第一章 绪论
动态规划并非数据结构，而是算法，是一种思想，解决某一类问题的思想。
比如先易后难就算是一种思想。
我们用一道题来引入动态规划。
LeetCode 120 三角形最小路径和
这道题我们先抛开递归不谈，先用之前的方法来做。对于上节学到的二叉树的解法：80-90%的题目就是Divide & Conquer，还有一小部分是用traverse。这两种方法都是DFS，都是递归。
解法一：DFS-Traverse
如果这道题是：给你一棵二叉树，请问，从根节点出发，走到下面的最大路径之和是多少，该怎么做呢？
// 走到当前节点的前面节点的和void dfs_tarverse(TreeNode root, sum) {if (root == null) {if (MAXNUM < sum) {MAXSUM = sum;}return;}dfs(root.left, sum + root.val);dfs(root.right, sum + root.val);}// 调用{int MAXSUM = Integer.MIN_VALUE;dfs_traverse(root, 0);return MAXSUM;}
我们看看，上面这个题和下面这个题是一模一样的。其实对于traverse这种题目：我想多少几点，让我们对其体会加深，让我们以后用的得心应手一点。
tarverse理解
1.对于traverse这个模板要非常熟悉，知道其是做什么的！就是将一个类似树的东西遍历，遍历路径要非常明确。然后就是一直深度搜索什么时候是头呢？(也是递归出口)，就是遇到null的时候，当然你也可以设置是叶子节点的时候。而往往这个时候就是我们一顿操作的时候。其次，就是我们每一个点都可以记录住从根节点到这一个节点发生的一些事情，比如这里的sum。
2.就是不要将tarvease理解成递归，就是tarverse，看到一道题目可以用tarverse解，就直接拿来用。
3.如何看一道题是否是tarverse：一般就是将从上到下视为一条路径，然后从众多路径中找到一个什么。
4.tarverse也是递归，但是不要用递归去理解。
我们上节课说过，对于tarverse，将要变化的那些东西，都变成参数作为方法的形参，然后传来传去。
函数定义：从根节点出发，走到当前节点之前的路径和是sum。
// tarversevoid dfs(int x, int y, int sum) {if (x == n) {// found a whole path from top to bottomif (sum < best) {best = sum;}return;}traverse(x + 1, y, sum + A[x][y]);tarverse(x + 1, y + 1, sum + A[x][y]);}best = MAXINT;tarverse(0, 0, 0);// best is the answer
该算法的时间复杂度是O(2n)，因为这个树比较特殊。
对于二叉树，如图：从根节点到某个节点的路径只有一条。
而这个：从根节点到某节点的路径不止一条。
解法二：DFS-Divide & Conquer
对于tarverse，返回值是void，将变量以参数形式传来传去。
而分治算法是有返回值的，我们最好清晰地写出这个方法的定义是什么。
定义就是：从该节点出发的最小路径和。
// return the minimum path from (x, y) to bottomint dfs_divideConquer(int x, int y) {if (x == n) {return 0;}return min(dfs_divideConquer(x+1, y), dfs_divideConquer(x+1, y+1)) + a[x][y];}
复杂度是：O(2n)，复杂度还是如此。其实就是每次有两个选择，选择后每次还是两个选择。因此就2，然后2，即O(2n)。
优化解法
对于tarverse不好优化，也不能优化，因为tarverse的思想就是如此的。但对于Divide-Conquer，我们看看其慢在了哪里？
其实这个动规就像是带了脑子，这个脑子其实就是hash表。
只是这里的hash表更简单，可以用数组实现，key就是行与列；value就是到这一点的最小路径和。
记忆化搜索(Memorization)
上面是对于分治的缺陷和优化的讨论，现在我们开始优化，其实很简单，就是不要无脑返回了，你要记住每次返回的值，如果下次再求，如果记忆里已经有了，就直接用，而不是无脑再算一遍。
// return the minimum path form (x,y) to bottomint dfs_divide_conquer_memorization(int x, int y) {if (x == n) {return 0;}if (hash[x][y] != -1) {return hash[x][y];}hash[x][y] = min(dfs_divide_conquer_memorization(x+1,y), dfs_divide_conquer_memorization(x+1, y+1)) + a[x][y];return hash[x][y];}
记忆化搜索本质 - 动态规划
记忆化搜索：本质上就是 动态规划。
动态回话就是 解决了重复计算 的搜索
动态规划的实现方式：
1.记忆化搜索 — 写法还是递归，但是其实已经是动规了。但是准确说还是叫记忆化搜索
2.循环
其实记忆化搜索相较于循环自然是要栈空间的，多了许多的内存开销。
对于分治：其实就是我们要计算根节点结果；其依赖下面两个节点，因此要计算下面两个节点；而下面的两个节点又依赖更下面的四个节点，因此要先算下面的四个节点。
记忆化搜索是：如果有重复节点(对于二叉树自然是没有重复的，但对于这道题的数组可以有重复的，就可以用记忆化搜死)。再每个节点计算好后，记录下来，如果下次还计算这个节点，就从记忆中查找。
循环：记忆化搜索怎么这么婆婆妈妈的，你要计算一个点，要依赖下面的两个点，再依赖更下面的三个点。那我就直接先计算下面的三个，然后再计算第二层的两个，再计算根节点。这样也省去了大量的栈开销。
循环 - 动态规划
对于Divide-Conquer，我们要定义这个函数的作用是什么，尤其是返回值。因此对于循环，我们也要定义这个数组的作用，即到这个节点其里面存的值是什么含义，即hash表是什么含义。
f[i][j]表示：从当前节点出发，走到最后一层的最小sum。
初始化：自然是走后一层就是数组本来的值。
循环：从下网上，从左往右
自底往上 循环 动态规划
从下往上算，先算离终点最近的一层。
A[][]
// 状态定义
f[i][j] 表示从i，j出发走到最后一层的最小路径长度
// 初始化，终点线有值
for (int i = 0; i < n; i++) {
f[n-1][i] = A[n-1][i];
}
// 循环递推求解
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
f[i][j] = Math.min(f[i+1][j], f[i+1][j+1]) + A[i][j];
}
}
// 求结果：起点
f[0][0]
自顶向下 循环 动态规划
这道题自顶向下要稍微复杂一点点。因为自底向上的话，从该点向下一定能够找到两条确定的路径。
但是自顶向下，算某一点时，该点可能来自上方的两个点(但要判断边界)。
这道题是初始化简单，但求答案难点。
// 自顶向下的总台规划
状态定义：
f[i][j] 表示从0,0出发，到达i，j的最短路径是什么
// 初始化
f[0][0] = A[0][0]
// 递归求解
for (int i = 1; i < n; i++) {
for (int j = 1; j <= i; j++) {
f[i][j] = ∞;
if (i - 1, j存在) {
if[i][j] = min(f[i][j], f[i-1][j]);
}
if (i - 1, j - 1存在) {
...
}
f[j][j] += A[i][j];
}
}
// 答案
min(f[n-1][0], f[n-1][1], f[n-1][2] ...)
后面讲的题目都是自顶向下来的，这样顺点，当然你也可以用自底向上。
循环求解 VS 记忆化搜索
循环求解更正规，存在空间优化的可能，大多数面试官可以接受。
记忆化搜索空间耗费更大，但思维难度小，编程难度小，时间效率很多情况下更高，少数有水平的面试官可以接受。
自顶向下 VS 自底向上
两种方法没有太大优劣区别
思维模式一个正向，一个逆向
为了方便教学，后面我们统一采用自顶向下的方式
什么情况下可能是动态规划
满足下面三个条件之一（这是经验，不一定是100%准确，但90%如此）
1.Maximum/Minimum 比如：从上到下的最大值路径
2.Yes/No 比如：从上到下能不能找到一条路径
3.Count() 比如：从上到下一共有多少种走法
则”*极有可能“是使用动态规划求解
并且还需要 Can not sort / swap，比如这道题就满足第一种情况，求最大值，但是这个数组是不能交换的，也不能排序的。
什么情况下可能不是动态规划？
如果题目需要求出所有”集体”的方案而非方案”个数”
LeetCode 131 分割回文串
输入数据是一个”集合”而不是”序列”
LeetCode 128 最长连续序列
动态规划的4点要素
1.状态State
灵感，创造力，存储小规模问题的结果
2.方程Function
状态之间的联系，怎么通过小的状态，来算大的状态
3.初始化Intialization
最极限的小状态是什么，起点
4.答案Answer
最大的那个状态是什么，终点
面试中常见的动态规划
1.Matrix DP (15%)
2.Sequence (40%)
3.Two Sequences DP (40%)
4.Others (5%)
对于这四种类型：我们有固定的状态State，这个已经帮大家解决了。
下面只需要自己推理出后面三条即可。
第二章 Matrix DP
这种题给你的就是矩阵，或者像上面的那种半个矩阵，反正是有坐标的概念。
state：f[x][y]标识我从起点走到坐标x，y…..
function：研究走到x，y这个点之前的一步
intialize：起点
answer：终点
刷题第一站 从左上角到右下角的最大最小路径和、路径个数
LeetCode 最小路径和
class Solution {
/**
* f[i][j] 表示：从起点到grid[i][j]点的最小路径和
* 转移方程：min(f[i][j-1], f[i-1][j]) + grid[i][j]
* 初始化：第一行和第一列
* 结果：f[m-1][n-1]
*/
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length, cols = grid[0].length;
int[][] f = new int[rows][cols];
// 初始化
f[0][0] = grid[0][0];
for (int i = 1; i < cols; i++) {
f[0][i] = f[0][i-1] + grid[0][i];
}
for (int j = 1; j < rows; j++) {
f[j][0] = f[j - 1][0] + grid[j][0];
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
f[i][j] = grid[i][j] + Math.min(f[i-1][j], f[i][j-1]);
}
}
return f[rows-1][cols-1];
}
}
LeetCode 62 不同路径
class Solution {
/*
* f[i][j] : 从起点到A[i][j] 共有多少种走法
* 转义方程：f[i][j] = f[i-1][j] + f[i][j-1]
* 初始化：第一行和第一列
* 结果：f[m-1][n-1]
*/
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
int[][] f = new int[m][n];
for (int i = 0; i < m; i++) {
f[i][0] = 1;
}
for (int j = 0; j < n; j++) {
f[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
f[i][j] = f[i-1][j] + f[i][j-1];
}
}
return f[m-1][n-1];
}
LeetCode 63 不同路径 II
class Solution {
/**
* f[i][j]:表示从起点到达A[i][j]总共有多少条路径
* 转移方程： 如果当前节点是非阻塞点：f[i][j] = f[i-1][j] + f[i][j-1];
* 如果当前节点是阻塞点f[i][j] = 0;
* 初始化：第一行，和第一列：但是，请注意：如果第一行或者第一列有阻塞点，则该行或列的后面都是0
* 最终结果f[m][n]
*/
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
return 0;
}
int rows = obstacleGrid.length, cols = obstacleGrid[0].length;
int[][] f = new int[rows][cols];
// 初始化
int i = 0;
for (; i < rows; i++) {
if (obstacleGrid[i][0] == 1) {
break;
}
f[i][0] = 1;
}
for (; i < rows; i++) {
f[i][0] = 0;
}
int j = 0;
for (; j < cols; j++) {
if (obstacleGrid[0][j] == 1) {
break;
}
f[0][j] = 1;
}
for (; j < cols; j++) {
f[0][j] = 0;
}
for (int m = 1; m < rows; m++) {
for (int n = 1; n < cols; n++) {
if (obstacleGrid[m][n] == 1) {
f[m][n] = 0;
} else {
f[m][n] = f[m-1][n] + f[m][n-1];
}
}
}
return f[rows-1][cols-1];
}
}
221. 最大正方形
class Solution {
public int maximalSquare(char[][] matrix) {
int maxSide = 0;
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
return maxSide;
}
int rows = matrix.length, cols = matrix[0].length;
int[][] dp = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
}
1277. 统计全为 1 的正方形子矩阵
class Solution {
public int countSquares(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
return 0;
}
int rows = matrix.length, cols = matrix[0].length;
int count = 0;
int[][] dp = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 1) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
}
count += dp[i][j];
}
}
return count;
}
}
第三章 Sequence DP
这种题一般是给你一个一维数字、n个数字、n个字母、n个位置(比如n个台阶)，就像一个序列一般。
state：f[i]表示“前i”个位置/数字/字母，(以第i个为)…
function：f[i] = f[j] … j是i之前的一个位置
intialize：f[0]..
answer：f[n-1]..
刷题第一站
70. 爬楼梯
class Solution {
public int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int f0 = 0, f1 = 1;
for (int i = 2; i <= n; i++) {
int num = f0 + f1;
f0 = f1;
f1 = num;
}
return f1;
}
}
LeetCode 70 爬楼梯
这道题你也可以不认为是动规，因为不是非常明显。
class Solution {
/**
* state:f[i]表示前i个位置，跳到第i个位置的方案总数
* function：f[i] = f[i-1] + f[i-2];
* intialize：f[0] = 1, f[1] = 1
* answer：f[n]
*/
public int climbStairs(int n) {
int a = 1, b = 2;
if (n == 1) return a;
if (n == 2) return b;
for (int i = 3; i <= n; i++) {
int temp = b;
b += a;
a = temp;
}
return b;
}
}
LeetCode 55 跳跃问题
这道题可以用贪心解，而且其复杂度是最低的。但是这里我们用动态规划求解。
这道题满足动规的可能：
1.yes/no 即能否跳到最后
2.数组不可调换位置，不可排序 因为每个地方都代表一定含义，这个位置可以跳几步
下面，这个题目始于四种类型中的哪一种？
序列性动态规划
class Solution {
/**
* state：f[i]代表我能否从起点跳到第i个位置
* function：f[i] = OR(f[j], j < i && j能够跳到i)
* initialize：f[0] = true;
* answer：f[n-1]
*/
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int length = nums.length;
boolean[] f = new boolean[length];
// 初始化
f[0] = true;
for (int i = 1; i < length; i++) {
for (int j = 0; j < i; j++) {
if (f[j] == true && nums[j] >= (i - j)) {
f[i] = true;
break;
}
}
}
return f[length - 1];
}
}
LeetCode 45 跳跃问题 II
这道题满足动规的可能：
1.Maximum/Minimum
2.不可排序和调换位置
下面，这个题目始于四种类型中的哪一种？
序列性动态规划
class Solution {
/**
* state：f[i]代表我跳到这个位置最少需要几步
* function：f[i] = MIN(f[j]+1, j < i && j能够跳到i)
* initialize：f[0] = 0;
* answer：f[n-1]
*/
public int jump(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
int[] f = new int[length];
// f[0] = 0; 这个初始化不用写
for (int i = 1; i < length; i++) {
f[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
if (f[j] != Integer.MAX_VALUE && nums[j] >= (i-j)) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
return f[length-1];
}
}
这道题一定要明白，我们给f[i]数组赋值为Integer.MIN_VALUE的含义。
如果程序写成下面这样，应该会更好理解一点。
// version 1: Dynamic Programming
// 这个方法，复杂度是 O(n^2)，会超时，但是依然需要掌握。
public class Solution {
public int jump(int[] A) {
// state
int[] steps = new int[A.length];
// initialize
steps[0] = 0;
for (int i = 1; i < A.length; i++) {
steps[i] = Integer.MAX_VALUE;
}
// function
for (int i = 1; i < A.length; i++) {
for (int j = 0; j < i; j++) {
if (steps[j] != Integer.MAX_VALUE && j + A[j] >= i) {
steps[i] = Math.min(steps[i], steps[j] + 1);
}
}
}
// answer
return steps[A.length - 1];
}
}
746. 使用最小花费爬楼梯
class Solution {
public int minCostClimbingStairs(int[] cost) {
if (cost.length == 1) return cost[0];
if (cost.length == 2) return cost[0] < cost[1] ? cost[0] : cost[1];
int[] dp = new int[cost.length];
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < cost.length; i++) {
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
}
return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
}
}
343. 整数拆分
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
for (int i = 2; i <= n; i++) {
int curMax = 0;
for (int j = 1; j < i; j++) {
curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
}
dp[i] = curMax;
}
return dp[n];
}
}
96. 不同的二叉搜索树
class Solution {
public int numTrees(int n) {
int[] G = new int[n + 1];
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
G[i] += G[j - 1] * G[i - j];
}
}
return G[n];
}
}
LeetCode 132 分隔回文串 II （未完成）
这道题满足动规的可能：
1.Maximum/Minimum 求最少分隔次数
2.不可排序和调换位置 你这个字符串中的字符换位置没有任何意义
下面，这个题目始于四种类型中的哪一种？
序列性动态规划 可以把字符串当作一个sequence
class Solution {
/**
* state：f[i]“前i”个字符组成的子字符串需要最少几次cut(最少能被分隔为多少字符串-1)
* function: f[i] = MIN{f[j] + 1, j<i && j+1 ~ i这一段是一个回文串}
* intizlize:f[i] = i - 1 (f[0] = -1)
* answer：f[s.length()]
*/
public int minCut(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[] cut = new int[s.length()+1];
boolean[][] isPalindrome = getIsPalindrome(s);
cut[0] = 0;
cut[1] = 1;
for (int i = 2; i <= s.length(); i++) {
cut[i] = Integer.MAX_VALUE;
for (int j = 1; j <= i; j++) {
if (isPalindrome[j-1][i-1] && cut[j-1] != Integer.MAX_VALUE) {
cut[i] = Math.min(cut[i], cut[j-1] + 1);
}
}
}
return cut[s.length()] - 1;
}
private static boolean[][] getIsPalindrome(String s) {
boolean[][] isPalindrome = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
isPalindrome[i][i] = true;
}
for (int i = 0; i < s.length() - 1; i++) {
isPalindrome[i][i+1] = (s.charAt(i) == s.charAt(i+1));
}
for (int col = 2; col < s.length(); col++) {
for (int row = 0; row < col - 1; row++) {
isPalindrome[row][col] = isPalindrome[row+1][col-1] && (s.charAt(row) == s.charAt(col));
}
}
return isPalindrome;
}
}
上面这道题好好说道一下：
1.这里判断一个字符串是不是回文串，我们用了动态规划的方法；并且我们将判断是否是回文串这个内容放到了外面，而非在计算f[i]中。这是为什么的呢？因为如果放在f[i]中，则复杂度瞬时上升到了O(n3)。如果放在外面，是2O(n2)，其实还是O(n2)。
2.这里判断是否是回文串用了动态规划的方法，当然你也可以不用的。这里用动态规划解法：如下题所示：可以看一下，尤其是计算顺序。计算时，要一列一列从左到右计算。
3.这里计算时，我们设置f[]数组时长度是s.length() + 1；这样可以为空串设置一个地方，会减少很多麻烦。
4.该题要记会哦。
LeetCode 125 验证回文串
当然这道题用动态规划解是超时的。但是如果是辅助上一道题，计算字符串中每个字符串是否是回文串就非常好了。
class Solution {
/**
* f[i][j]表示：字符串从第i个字符到第j个字符是否是回文串，当然i<=j
* f[i][j] = charAt(i) == charAt(j) && f[i+1][j-1] == true
* 初始化，整个斜线代表一个字母要初始化为true，紧挨着的第二条斜线，即两个字符，要初始化为 字符A == 字符B
* 结果：f[0][s.length()-1]
*/
public boolean isPalindrome(String s) {
if (s == null) {
return false;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9')) {
sb.append(ch);
}
}
s = sb.toString().toLowerCase();
if (s.length() == 0) return true;
int length = s.length();
boolean[][] isPalindrome = new boolean[length][length];
for (int i = 0; i < length; i++) {
isPalindrome[i][i] = true;
}
for (int i = 0; i < length - 1; i++) {
isPalindrome[i][i+1] = (s.charAt(i) == s.charAt(i+1));
}
for (int col = 2; col < length; col++) {
for (int row = 0; row < col - 1; row++) {
isPalindrome[row][col] = (s.charAt(row) == s.charAt(col)) && isPalindrome[row+1][col-1];
}
}
return isPalindrome[0][length-1];
}
}
LeetCode 139 单词拆分
这道题和上一道题非常相似(LeetCode 132)。
1.两道题解法几乎一模一样，只是其中一个是在两个循环内判断从j到i是否是回文串，而这个则是在O(n)时间内判断一下是否存在于字典中。
2.两道题目设置的dp[]都是s.length() - 1;
按道理应该先分析这道题是不是动态规划题目的，但是上面还是先写了和上道题的渊源，现在判断一下这道题目是否是动态规划，以及属于哪种都太规划。
1.yes/no 是否问题，能力问题，可以与否
2.字符串不可排序与换位
又是一个字符串，因此是Sequence DP。
本题的小track：由于一个字符串是可能很长的，但是一个单词绝不不会很长，比如我们常见的单词”international”也无非13个字符。所有，我们在计算dp[i]时，可以最多计算i-13个长度即可，无需从0~i都计算了。因此就需要知道这个字典中最长单词的length，复杂度时O(n2)。而如哦按照原本的，复杂度则是O(n3)。
class Solution {
/**
* dp[i]表示：前i个字符是否可以拆分成一个或多个在字典中出现的单词
* dp[i] = 任意一个满足[j~i存在于字典中，dp[j-1] && j < i]
* 初始化dp[0] = true
* answer：dp[length+1]
*/
public static boolean wordBreak(String s, List<String> wordDict) {
if (s == null) return false;
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
dp[i] = false; // 这句话可不写，因为本身初始化就是false
for (int j = 1; j <= i; j++) {
if (wordDict.contains(s.substring(j - 1, i+1 - 1)) && dp[j-1]) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
140. 单词拆分 II
这道题再好好品味下，这是我的代码，没有完全通过。
这个题解非常清晰，还要配合官网题解。
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
List<List<String>> res = dfs(s, 0, new HashSet<String>(wordDict), new HashMap<Integer, List<List<String>>>());
List<String> ans = new ArrayList<String>();
for (List<String> words : res) {
ans.add(String.join(" ", words));
}
return ans;
}
private List<List<String>> dfs(String s, int index, Set<String> wordSet, Map<Integer, List<List<String>>> memory) {
if (memory.containsKey(index)) {
return memory.get(index);
}
if (index >= s.length() - 1) {
List<List<String>> temp = new LinkedList<>();
List<String> t = new LinkedList<>();
temp.add(t);
return temp; // [[]]
}
List<List<String>> wordBreaks = new LinkedList<List<String>>();
for (int i = index + 1; i <= s.length(); i++) {
String word = s.substring(index, i);
if (wordSet.contains(word)) {
List<List<String>> nextWordBreaks = dfs(s, i, wordSet, memory);
for (List<String> nextwordBreak : nextWordBreaks) {
LinkedList<String> wordBreak = new LinkedList<String>(nextwordBreak);
wordBreak.offerFirst(word);
wordBreaks.add(wordBreak);
}
}
}
memory.put(index, wordBreaks);
return wordBreaks;
}
}
下方这个是官网代码。
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Map<Integer, List<List<String>>> map = new HashMap<Integer, List<List<String>>>();
List<List<String>> wordBreaks = backtrack(s, s.length(), new HashSet<String>(wordDict), 0, map);
List<String> breakList = new LinkedList<String>();
for (List<String> wordBreak : wordBreaks) {
breakList.add(String.join(" ", wordBreak));
}
return breakList;
}
public List<List<String>> backtrack(String s, int length, Set<String> wordSet, int index, Map<Integer, List<List<String>>> map) {
if (!map.containsKey(index)) {
List<List<String>> wordBreaks = new LinkedList<List<String>>();
if (index == length) {
wordBreaks.add(new LinkedList<String>());
}
for (int i = index + 1; i <= length; i++) {
String word = s.substring(index, i);
if (wordSet.contains(word)) {
List<List<String>> nextWordBreaks = backtrack(s, length, wordSet, i, map);
for (List<String> nextWordBreak : nextWordBreaks) {
LinkedList<String> wordBreak = new LinkedList<String>(nextWordBreak);
wordBreak.offerFirst(word);
wordBreaks.add(wordBreak);
}
}
}
map.put(index, wordBreaks);
}
return map.get(index);
}
}
总结
1.对于Sequence DP，如果是字符串，则可能要多设置一个dp[]位置，即为空川留位置，此时就要注意，字符串的位置和dp的位置是差1的。
2.。。。。
LeetCode 300 最长递增子序列
这道题放在这里，是因为有一定的难度。
动态给i话特征：
1.Maximum/Minumum
2.不可排序和swap
又是字符串，因此是sequence。因此就是sequence DP。
这道题是如何的符合动态规划的特征。
但是呢？
这道题的状态，如果还是按照上面的方法设计，即
错误的方法：f[i]表示前i个数字中最长的LIS的长度
正确的方法：f[i]表示前i个数字中以第i个结尾的LIS的长度
function：f[i] = Max{f[i] + 1 && a[j] <= a[i]}
intialize：f[0..n-1] = 1
answer：max(f[0..n-1])
说明：
这里借助原有的f[i]定义，很难找到f[i]和前面状态的联系；
最后计算答案时会麻烦一些：用O(n)的时间计算出最大值。
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = 1;
int max = dp[1];
for (int i = 2; i <= nums.length; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (nums[i-1] > nums[j-1]) {
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
}
反思：
对于分隔回文串II，如果可以分割成功，则一定包含最后一个字母；
对于单词拆分，如果可以拆分成功，则一定包含最后一个字母；
而！！
对于最长递增子序列，如果找到这个子序列，未必会包含最后一个单词。因此这里的定义dp[i]表示以i字符结尾的最长递增子序列，最后用O(n)获得最长值。
198. 打家劫舍
这是自己写的，虽然通国了，但是写了一个多此一举的一行！！
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length < 2) {
return Math.max(nums[0], nums[nums.length - 1]);
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
int max = dp[0];
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(nums[i] + max, Math.max(max, dp[i - 1]));
max = Math.max(max, dp[i - 1]);
}
return dp[nums.length - 1];
}
}
这是官网的
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
}
}
第四章 Two Sequence DP
小插曲 Recursive VS DP
递归是一种程序的实现方式：函数的自我调用
Function(x) {
...
Function(x-1);
...
}
动态规划是一种解决问题的思想：大规模问题的结果，是由小规模问题的结果运算得来的。动态规划可以用递归来实现(Memorization Search)。
Two Sequence Dp这种题目一般是给你两个字符串，或者是两个数组。当然给你两个字符串的最多。
state：f[i][j]代表了第一个sequence的前i个数字/字符 配上第二个sequence的前j个…
function：f[i][j] = 研究第i个和第j个的匹配关系
intialize：f[i][0]和f[0][i]
answer:f[s1.length()][s2.length()]
LeetCode 1143 最长公共子序列
state：f[i][j]表示前i个字符匹配上前j个字符的LCS的长度
function：
f[i][j] = MAX(f[i-1][j], f[i][j-1], f[i-1][j-1]) // a[i] = a[j]
= MAX(f[i-1][j], f[i][j-1]) // a[i] != a[j]
intialize：f[i][0] = 0
f[0][j] = 0
answer：f[a.length()][b.length()]
说明：
对于f[i][j]的结果，即第一个字符串前i个字符，第二个字符串前j个字符，组成的最长公共子序列。一定会大于f[i][j-1,j-2…]和f[i-1,i-2…][j]。而f[i][j]的值一定来自于f[i][j-1,j-2…]或f[i-1,i-2…][j]或者f[i-1][j-1]。而f[i-1][j-1]又来自于f[i-1][j-2,j-3…]或f[i-2,i-3…][j-1]或f[i-2][j-2]。以此类推，让f[i][j]来自于Max(f[i][j-1],f[i-1][j],f[i-1][j-1])则将是全局最大值。当然了，我们知道显然f[i][j-1]≥f[i-1][j],f[i-1][j-1]) && f[i-1][j] ≥ f[i-1][j-1]。这里的f[i][j] = Max(f[i][j-1],f[i-1][j],f[i-1][j-1])要不要写f[i-1][j-1]，要看s1[i]是否等于s2[j]。如果相等，则为f[i-1][j-1]的存在提供了可能，因为此时f[i][j]是可能为f[i-1][j-1]+1的，当然还是要在三者中取最大值，因为f[i-1][j-1]+1未必还是最大的一个；如果s1[i]!=s2[j]，那么这个最大值里面就没有必要存在f[i-1][j-1]了。
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
if (text1 == null || text2 == null) {
return 0;
}
int[][] dp = new int[text1.length()+1][text2.length()+1];
for (int i = 0; i <= text1.length(); i++) {
dp[i][0] = 0;
}
for (int i = 0; i <= text2.length(); i++) {
dp[0][i] = 0;
}
for (int i = 1; i <= text1.length(); i++) {
for (int j = 1; j <= text2.length(); j++) {
int max = Math.max(dp[i-1][j], dp[i][j-1]);
dp[i][j] = text1.charAt(i-1) == text2.charAt(j-1)? Math.max(max, dp[i-1][j-1]+1): max;
}
}
return dp[text1.length()][text2.length()];
}
}
LintCode 79 最长公共子串
题目：
给出两个字符串，找到最长公共子串，并返回其长度。
分析：
1.Maximum/Minimum
2.不可排序/swap
又是两个子串，因此是two sequence DP。
错误state：f[i][j]表示第一个字符串前i个字符组成的字符串，第二个字符串前j个字符组成的字符串，其最长公共子串。用这个state很难描述f[i][j]与前面的关系
state:f[i][j]表示前i个字符配上前j个字符的LCS的长度(一定以第i个和第j个结尾的LCS)
function：f[i][j] = f[i-1][j-1] // a[i] = b[j]
= 0 // a[i] != b[j]
intialize:f[i][0] = 0 f[0][j]=0
answer:MAX(f[0..a.length()][0..b.length()])
public class Solution {
/**
* @param A: A string
* @param B: A string
* @return: the length of the longest common substring.
*/
public int longestCommonSubstring(String A, String B) {
// write your code here
if (A == null || B == null) {
return 0;
}
int[][] f = new int[A.length()+1][B.length()+1];
for (int i = 0; i <= A.length(); i++) {
f[i][0] = 0;
}
for (int i = 0; i <= B.length(); i++) {
f[0][i] = 0
}
int max = 0;
for (int i = 1; i <= A.length(); i++) {
for (int j = 1; j <= B.length(); j++) {
if (A.charAt(i-1) == B.charAt(j-1)) {
f[i][j] = f[i-1][j-1]+1;
}else {
f[i][j] = 0;
}
max = Math.max(max, f[i][j]);
}
}
return max;
}
}
说明：
这道题的state采用的是必须以i结尾和以j结尾的形式。如果以后我们遇到用平常所采用的state很难描述f[i][j]和前面状态的关系时，可以采用这种。
如果采用这种state，则最终答案是遍历获得最大值。
LeetCode 72 编辑距离
state:f[i][j]a的前i个字符最少要用几次编辑可以变成b的前j个字符
function:
f[i][j] = MIN(f[i-1][j]+1, f[i][j-1]+1,f[i-1][j-1]) // a[i] == b[j]
= MIN(f[i-1][j]+1, f[i][j-1]+1,f[i-1][j-1] + 1) // a[i] != b[j]
intialize:f[i][0] = i, f[0][j] = j
answer:f[a.length()][b.lengtg()]
说明：
对于上面这三道Two Sequence DP，除了第二道是以i和j结尾声明state，剩下这两个都是常规的state，即以问题本身声明的state。我们发现在寻找关系时，即function，f[i][j]都是在f[i][j-1]、f[i-1][j]、f[i-1][j-1]中寻找关系。
对于这道题，其实就是：
如果a[i] == b[j]
要么是f[i-1][j-1]，即a的前i-1个字符变成b的前j-1个字符的最少编辑次数
要么是f[i-1][j]+1，即a的前i-1个字符变成b的前j个字符的编辑次数，然后+1(即a添加一个字符)
要么是f[i][j-1]+1，即a的前i个字符变成b的前j-1个字符的编辑次数，然后a这个字符串删除一个字符。
如果a[i] != b[j]
要么是f[i-1][j-1]+1，即a的前i-1个字符变成b的前j-1个字符，然后a上再替换1个字符
要是是f[i-1][j]，即a的前i-1个字符变成b的前j个字符，然后a上再删除一个字符
要么是f[i][j-1]，即a的前i个字符变成b的前j-1个字符，然后a上再删除一个字符。
class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) {
return 0;
}
int[][] f = new int[word1.length()+1][word2.length()+1];
for (int i = 0; i <= word1.length(); i++) {
f[i][0] = i;
}
for (int i = 0; i <= word2.length(); i++) {
f[0][i] = i;
}
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
if (word1.charAt(i-1) == word2.charAt(j-1)) {
f[i][j] = Math.min(Math.min(f[i-1][j-1], f[i-1][j]+1), f[i][j-1]+1);
} else {
f[i][j] = Math.min(Math.min(f[i-1][j-1] + 1, f[i-1][j]+1), f[i][j-1]+1);
}
}
}
return f[word1.length()][word2.length()];
}
}
LeetCode 115 不同的子序列
state：f[i][j]表示a的前i个字符中选取b的前j个字符，有多少种方案。
function：
f[i][j] = f[i-1][j] + f[i-1][j-1] (a[i] == b[j])
= f[]i-1[j] (a[i] != b[j])
intialize:f[i][0] = 1, f[0][j] = 0 (j>0)
answer：f[n][m]
class Solution {
public int numDistinct(String s, String t) {
if (s == null || t == null) {
return 0;
}
int[][] nums = new int[s.length()+1][t.length()+1];
for (int i = 0; i <= s.length(); i++) {
nums[i][0] = 1;
}
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= t.length(); j++) {
nums[i][j] = nums[i-1][j];
if (s.charAt(i - 1) == t.charAt(j - 1)) {
nums[i][j] += nums[i - 1][j - 1];
}
}
}
return nums[s.length()][t.length()];
}
}
LeetCode 97 交错字符串
state:f[i][j]表示s1的前i个字符和s2的前j个字符能否交替组成s3的前i+j个字符
function：f[i][j] = (f[i-1][j] && (s1[i-1] == s3[i+j-1]) || f[i][j-1] && (s2[j-1] == s3[i+j-1]))
intialize：f[i][0] = s1[0..i-1] = s3[0..i-1]
f[0][j] = s2[0..j-1] = s3[0..j-1]
answer：f[n][m]
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s2 == null) {
return false;
}
if (s1.length() + s2.length() != s3.length()) {
return false;
}
boolean[][] f = new boolean[s1.length()+1][s2.length()+1];
f[0][0] = true;
for (int i = 1; i <= s1.length(); i++) {
if (s3.charAt(i - 1) == s1.charAt(i - 1) && f[i - 1][0]) {
f[i][0] = true;
}
}
for (int j = 1; j <= s2.length(); j++) {
if (s3.charAt(j - 1) == s2.charAt(j - 1) && f[0][j - 1]) {
f[0][j] = true;
}
}
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
// f[i][j] = false; 不需要写
f[i][j] = (s1.charAt(i - 1) == s3.charAt(i + j - 1) && f[i-1][j]) ||
(s2.charAt(j - 1) == s3.charAt(i + j - 1) && f[i][j-1]);
}
}
return f[s1.length()][s2.length()];
}
}
LeetCode 44 通配符匹配 (未完成)
这道题完全符合Two Sequence DP，可以用动态规划解。
题解
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
if (p.charAt(i - 1) == '*') {
dp[0][i] = true;
} else {
break;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
return dp[m][n];
}
}
10. 正则表达式匹配
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean f[][] = new boolean[m + 1][n + 1];
f[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
if (matches(s, p, i, j - 1)) {
f[i][j] = f[i - 1][j] || f[i][j - 2];
} else {
f[i][j] = f[i][j - 2];
}
} else {
if (matches(s, p, i, j)) {
f[i][j] = f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
private boolean matches(String s, String p, int i, int j) {
if (i == 0) {
return false;
}
if (p.charAt(j - 1) == '.') {
return true;
}
return s.charAt(i - 1) == p.charAt(j - 1);
}
}
第五章 背包问题
LintCode 92 背包问题
这道题是一道比较典型的背包问题的描述。
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]
样例 1:
输入: [3,4,8,5], backpack size=10
输出: 9
样例 2:
输入: [2,3,5,7], backpack size=12
输出: 12
这是一道痕典型的背包问题的描述：你有一个固定大小的背包，最多能装多少。
首先分析这道题是不是动态规划。
似乎还不满足动态规划，因为这个数组里面的数字是一个即可，没有顺序的区分，你可以随意swap。你可能因此觉得不是动态规划。
确实，严格来说，背包问题说它是动态规划有那么一点牵强，因为其在最坏情况下是一个搜索，与搜索等价。也就是在最坏情况下，它是没有重复方案的。
如果这道题你去用搜索去做，其实是很平常的一道题目，其实就是subsets的一个问题。你决策以下每个数要不要，然后看罪接近m的数是多少。这是一个很典型的subsets问题。直接对应到subsets那道题的解法。
但是这道题确实可以用动态规划来做，因为体积m可能是很小的，组成m的方案可能有很多。拿[2,3,5,7]来说，组成5的方案就有[2,3]和[5]这两种方案。如果你用搜索做，你会去试[2,3]+7和[5]+7，这时候对于7而言，不管你加的是[2,3]也好，还是[5]也好，两个加的都是5，无所谓加的具体是谁，因为它只关心它加的那个和是多少。
所以这样子就存在一个优化的空间，拿[2,3,5,7]来说，对于前3个数，它组成5的方案，我只关心yes OR no，只关心前三个数能不能组成5。如果前3个数能组成5，那么前4个数就能组成12，我并不关心5这个数组是[2,3]来的，还是[5]来的。
这就是动态规划能用于背包问题进行优化的一个原因。就是把不关心具体方案，我只关心最后的那个value。
n个整数a[1..n]，装m的背包
state：f[i][j] "前i"个数，取出一些能否组成和为j
function：f[i][j] = f[i-1][j] or f[i-1][j-a[i]]
intialize:f[X][0] = true; f[0][1..m] = false;
answer：能够使得f[n][X]最大的X(0<=X<=m) 倒着来找
public class Solution {
public int backPack(int m, int[] A) {
boolean f[][] = new boolean[A.length + 1][m + 1];
for (int i = 0; i <= A.length; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = false;
}
}
f[0][0] = true;
for (int i = 0; i < A.length; i++) {
for (int j = 0; j <= m; j++) {
f[i + 1][j] = f[i][j];
if (j >= A[i] && f[i][j - A[i]]) {
f[i + 1][j] = true;
}
} // for j
} // for i
for (int i = m; i >= 0; i--) {
if (f[A.length][i]) {
return i;
}
}
return 0;
}
}
背包问题很特别，不过我们一般也很好看出来，如果要求的结果是和集合里面的几个元素的和相关的，一般就可以归于背包问题。
此外，背包问题要求的是maximum/minimum
但是在定义时，确实true/false，即yes/no
用滚动数组优化
关于上面的背包问题算法的优化，其实f[i][j]只和上一行相关，因此可优化为：
public class Solution {
public int backPack(int m, int[] A) {
boolean f[][] = new boolean[2][m + 1];
for (int i = 0; i < 2; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = false;
}
}
f[0][0] = true;
for (int i = 0; i < A.length; i++) {
for (int j = 0; j <= m; j++) {
f[(i + 1) % 2][j] = f[i % 2][j];
if (j >= A[i] && f[i % 2][j - A[i]]) {
f[(i + 1) % 2][j] = true;
}
} // for j
} // for i
for (int i = m; i >= 0; i--) {
if (f[A.length % 2][i]) {
return i;
}
}
return 0;
}
}
对于上面的Matrix DP和Two Sequence DP，都可以用这种方式进行优化，如果f[i][j]只和这一行与上一行相关，则开辟两行数组，如果和这一行、上一行、上上一行相关，则开辟三行数组。如果只和本行相关，只开辟一行数组。对于程序很好改，还是按照原来的思路写下代码，然后在第一维的位置 % 数组的一维长度。
当然对于优化而言，还可以优化为一维数组，但是并不是非常通用，这里就不展示了。
下面所有题化为left+right=sum，其中left就是1，即选择的，left也是背包的大小。right是没有选择的石头！
416. 分割等和子集
链接
这道题要转化成和上道题一样的背包问题，这里也是没有物品价值，只有质量。
背包大小是sum / 2；在里面选出一部分和为sum / 2；上道题是最靠近target。因此返回结果略有差异。
另外，如果这里求出和为奇数，则直接返回false。
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) return false;
boolean[][] dp = new boolean[nums.length][sum / 2 + 1];
for (int i = 0; i < sum / 2 + 1; i++) {
if (nums[0] == i) {
dp[0][i] = true;
}
}
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < sum / 2 + 1; j++) {
dp[i][j] = dp[i - 1][j] || (j >= nums[i] && dp[i - 1][j - nums[i]]);
}
}
return dp[nums.length - 1][sum / 2];
}
}
1049. 最后一块石头的重量 II
本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int stone : stones) {
sum += stone;
}
boolean[][] dp = new boolean[stones.length][sum / 2 + 1];
dp[0][0] = true; // 不拿第一个石头
if (stones[0] < sum / 2 + 1) {
dp[0][stones[0]] = true; // 拿第一个石头
}
for (int i = 1; i < stones.length; i++) {
for (int j = 0; j < sum / 2 + 1; j++) {
dp[i][j] = dp[i - 1][j] || (j >= stones[i] && dp[i - 1][j - stones[i]]);
}
}
int res = Integer.MAX_VALUE;
for (int i = sum / 2; i >= 0; i--) {
if (dp[stones.length - 1][i]) {
res = Math.min(res, Math.abs(sum - i - i));
break;
}
}
return res;
}
}
494. 目标和
这道题目咋眼一看和动态规划背包啥的也没啥关系。
本题要如何使表达式结果为target，
既然为target，那么就一定有 left组合 - right组合 = target。
left + right等于sum，而sum是固定的。
公式来了， left - (sum - left) = target -> left = (target + sum)/2 。
target是固定的，sum是固定的，left就可以求出来。
此时问题就是在集合nums中找出和为left的组合。
题解一
题解二
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if ((target + sum) % 2 != 0) return 0;
int[][] dp = new int[nums.length][(target + sum) / 2 + 1];
dp[0][0] = 1;
if (nums[0] < (target + sum) / 2 + 1) {
dp[0][nums[0]] += 1; // 注意这里初始化时是+=，而不能只说是=，为什么呢？比如数据[0,0,0,0,0,0,0,0,1] target = 1
// 此时对于第一行，即第一个石头，不拿重量是0，拿也是0，因此dp[0][0]位置有两种方案
}
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < (target + sum) / 2 + 1; j++) {
dp[i][j] = j >= nums[i] ? dp[i - 1][j] + dp[i - 1][j - nums[i]] : dp[i - 1][j];
}
}
return dp[nums.length - 1][(target + sum) / 2];
}
}
474. 一和零
背包是二维的，暂时没作对！！
518. 零钱兑换 II
从这道题目开始，下面几道就是完全背包，即每块石头有多个！！
class Solution {
public int change(int amount, int[] coins) {
int[][] dp = new int[coins.length][amount + 1];
for (int i = 0; i < amount + 1; i += coins[0]) {
dp[0][i] = 1;
}
for (int i = 1; i < coins.length; i++) {
for (int j = 0; j < amount + 1; j++) {
int count = 0;
for (int k = j; k >= 0; k -= coins[i]) {
count += dp[i - 1][k];
}
dp[i][j] = count;
}
}
return dp[coins.length - 1][amount];
}
}
LintCode 125 Backpack II
这道题不仅考虑到每个物品的重量，还考虑到了其价值。
有n个物品和一个大小为m的背包。给定数组A表示每个物品的大小和数组V表示每个物品的价值
问最多能装入背包的总价值是多大？
A[i], V[i], n, m 均为整数
你不能将物品进行切分
你所挑选的要装入背包的物品的总大小不能超过 m
每个物品只能取一次
样例1：
输入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4]
输出: 9
解释: 装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9
样例2：
输入: m = 10, A = [2, 3, 8], V = [2, 5, 8]
输出: 10
解释: 装入 A[0] 和 A[2] 可以得到最大价值, V[0] + V[2] = 10
n个物品，背包为m，体积a[1..n]，价值v[1..n]
state：f[i][j]表示前i个物品中，取出"若干"物品后，体积"正好"为j的最大价值。
function：f[i][j] = max{f[i-1][j], f[i-1][j - a[i]] + v[i]}
intialize：f[x][0] = 0, f[0][1..m] = -∞
answer：f[n][1..m]中最大值
K数之和
这道题显然也是不完全符合动态规划的，但是符合背包问题(求集合中几个数的和)。因此可以上背包上想。
给定n个不同的正整数，整数K(K ≤ n) 以及一个目标数字target。
在这n个数里面找出k个数，使得k个数的和等于目标数字，求问有多少种方案？
样例1
输入:
List = [1,2,3,4]
k = 2
target = 5
输出: 2
说明: 1 + 4 = 2 + 3 = 5
样例2
输入:
List = [1,2,3,4,5]
k = 3
target = 6
输出: 1
说明: 只有这一种方案。 1 + 2 + 3 = 6
分析：
如果这道题没有k的个数限制，则
state:f[i][j]表示 前i个数，挑出若干，组成和为j，的方案总数
function：f[i][j] = f[i - 1][j - A[i]] + f[i-1][j]
当然这里呢？是由个数要求的
state：f[i][j]表示 前i个数，挑出j个数，组成和为t，的方案总数
state：f[i][j]前i个数取j个数出来能否和为t
function：f[i][j][t] = f[i-1][j-1][t-a[i]] + f[i-1][j][t] 要a[i] + 不要a[i]
1.问是否可行(DP) - f[x][0][0] = true
2.问方案总数(DP) - f[x][0][0] = 1
3.问所有方案(递归/搜索)
LintCode 91 最小调整代价
这道题你可能想不到是用动态规划去做的，但它却是是用动态规划来做的。
这道题却是有点难！！
给一个整数数组，调整每个数的大小，使得相邻的两个数的差小于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。
注意事项
你可以假设数组中每个整数都是正整数，且小于等于100。
样例
对于数组[1, 4, 2, 3]和target=1，最小的调整方案是调整为[2, 3, 2, 3]，调整代价之和是2。返回
这道题第一眼看上去非常符合 Sequence DP
public class Solution {
public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
sequence dp
给n个数， 不能调换，求最小
f[i] 表示前i个数调整到满足条件时的最小耗费
f[i] -> f[i - 1]
i变成了什么
i-1变成了什么
}
}
我们发现f[i]和f[i-1]很难发现联系，因为i-1的数即使调整成了最优，获得了f[i-1]，但是对于i而言，i-1的最优结构未必是i的最优结果。当一维无法解决时：
此时我们就将一维问题上升到二维
state：f[i][v]前i个数，第i个数调整为v，满足相邻两数≤target，所需要的的最小代价
function：f[i][v] = min(f[i-1][v'] + |A[i]-v|, |v-v'| ≤ target)
intialize:f[1][A[1]] = 0, f[1][A[1] +- X] = X
answer:f[n][X]
本题时间复杂度O(n*A*T)
第六章 其他DP类别的练习题 区间类
LintCode 硬币排成线 coins-in-a-line-iii
LintCode 430 攀爬字符串
若有收获，就点个赞吧
0 人点赞
