接下来的观察是关于题目性质的，可以发现我们最关注的是 “sum”，而不太关心这个 sum 是怎么来的。比如 sum = 10 的时候，我们可以取【2,3,5】 或者 【3,7】，虽然是两种不同的解，但是最终效果完全一样，也就是完全一样的“状态”。因此，如果我们用 sum 来定义状态，就会发现很多的 overlap subproblems，可以进一步采用记忆化搜索进行优化。
另一个需要注意的地方是，每个元素只能取一次，只有 “取” 或者 “不取” 的选择，因此当前 index 上的状态只能取决于之前的状态，而不能重复考虑当前元素。
dp[i][sum] = 前 i 个元素里我们能不能凑出来 sum.
dp[i][sum] 要么取决于 dp[i - 1][sum] (不取当前元素)
要么取决于 dp[i - 1][sum - nums[i]] (取当前元素)
其中每一行 i 都只考虑前一行 i - 1 的值。
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
public int backPack(int m, int[] A) {
// write your code here
// dp[i][j] for the first i elements, can we make sum of j
boolean[][] dp = new boolean[A.length + 1][m + 1];
for(int i = 0; i <= A.length; i++) dp[i][0] = true;
for(int i = 1; i <= A.length; i++){
for(int j = 1; j <= m; j++){
if(j - A[i - 1] >= 0)
dp[i][j] = (dp[i - 1][j] || dp[i - 1][j - A[i - 1]]);
else dp[i][j] = dp[i - 1][j];
}
}
for(int i = m; i >= 0; i--)
if(dp[A.length][i]) return i;
return -1;
}
}
考虑到我们只需要存最多两行的结果，滚动数组优化就显而易见了。
其实在背包九讲里面也有写过只存一行， 新一行的结果每次从右往左扫的，更经济些。简易程度上我还是更喜欢用取 mod 的滚动数组写法。
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
public int backPack(int m, int[] A) {
// write your code here
// dp[i][j] for the first i elements, can we make sum of j
boolean[][] dp = new boolean[2][m + 1];
for(int i = 0; i <= A.length; i++) dp[i % 2][0] = true;
for(int i = 1; i <= A.length; i++){
for(int j = 1; j <= m; j++){
if(j - A[i - 1] >= 0)
dp[i % 2][j] = (dp[(i - 1) % 2][j] || dp[(i - 1) % 2][j - A[i - 1]]);
else dp[i % 2][j] = dp[(i - 1) % 2][j];
}
}
for(int i = m; i >= 0; i--)
if(dp[A.length % 2][i]) return i;
return -1;
}
}
同时因为每次新迭代循环中， i 是不会走回头路的，所以状态与状态之间可以在不违反题意的情况下衔接起来。
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A & V: Given n items with size A[i] and value V[i]
* @return: The maximum value
*/
public int backPackII(int m, int[] A, int V[]) {
// write your code here
// dp[i][j] within first i elements with space j, maximum profit gain
int[][] dp = new int[A.length + 1][m + 1];
for(int i = 1; i <= A.length; i++){
for(int j = 1; j <= m; j++){
if(j - A[i - 1] >= 0){
dp[i][j] = Math.max(dp[i - 1][j] , dp[i - 1][j - A[i - 1]] + V[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[A.length][m];
}
}
仔细观察一下这题:
我们要凑出来一个和正好是 n 的选择组合；
能选的元素是固定数量的 perfect square (有的会超)
一个元素可以选多次；
这就是背包啊！
public class Solution {
public int numSquares(int n) {
// All perfect squares less than n
int[] dp = new int[n + 1];
Arrays.fill(dp, n + 1);
dp[0] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j * j <= n; j++){
if(i - j * j >= 0) dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}
背包类问题的马甲题。
每个元素可以取任意次；
只问最小的硬币数，就类似于 climbing stairs，只靠 sum 一个维度就可以了，但是循环依然是两层。
比较直观的写法是这样(内外循环的顺序无所谓，但是最好从 amount 那个维度开始)
public class Solution {
public int coinChange(int[] coins, int amount) {
// dp[n] = min number of coins to make amount n;
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for(int i = 1; i <= amount; i++){
for(int j = 0; j < coins.length; j++){
if(i - coins[j] >= 0) dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
比较优化和取巧的写法是这样，以面值
public class Solution {
public int coinChange(int[] coins, int amount) {
// dp[n] = min number of coins to make amount n;
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for(int j = 0; j < coins.length; j++){
for(int i = coins[j]; i <= amount; i++){
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
和背包 II 看起来结构一样，但是这次多了一个新条件：同一个元素可以取多次。
然而这个条件会带来一个重要的改变：元素的具体位置和数量都不重要了。我们可以直接扔掉这个维度，就像 Coin Change 和 Combination Sum IV 一样。
因此可以看到，只有对元素的选择(位置) / (数量)有限制性条件的 DP，才会需要另一个维度。
对位置有要求的，用 i 代表“前 i 个元素”；
对数量有要求的，用 j 代表“选 k 个元素”；
两个全有要求的，就两个维度都加上去。
两个维度都加上去，我们就有了 k sum 问题。
public class Solution {
/**
* @param A an integer array
* @param V an integer array
* @param m an integer
* @return an array
*/
public int backPackIII(int[] A, int[] V, int m) {
// Write your code here
// Maximum value we can get
int[] dp = new int[m + 1];
for(int i = 0; i < A.length; i++){
for(int j = 1; j <= m; j++){
if(j - A[i] >= 0)
dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
}
}
return dp[m];
}
}
注意这里内外循环的顺序不能错，要先按 sum 从小到大的顺序看，然后才是遍历每个元素。因为所谓 bottom-up，是相对于 sum 而言的，不是相对于已有元素的 index 而言的。
可以看到，在只取 min/max 的时候我们不同的循环顺序都能保证正确答案；但是求解的数量时，要以 target value 为外循环。
public class Solution {
public int combinationSum4(int[] nums, int target) {
// dp[sum] = number of ways to get sum
int[] dp = new int[target + 1];
// initialize, one way to get 0 sum with 0 coins
dp[0] = 1;
for(int j = 1; j <= target; j++){
for(int i = 0; i < nums.length; i++){
if(j - nums[i] >= 0) dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}
}
背包类问题的扩展版本~
我们关注的维度有三个：
前 i 个元素，因为一个元素只能选一次；
选了 j 个元素，因为我们要求选 k 个数；
总和 sum，用于每次试图添加新元素时用来查询。
时间：O(len * k * target)，三重循环
空间：O(k * target)
public class Solution {
/**
* @param A: an integer array.
* @param k: a positive integer (k <= length(A))
* @param target: a integer
* @return an integer
*/
public int kSum(int A[], int k, int target) {
// int[i][j][k] : number of ways to get sum of k by picking
// j numbers from first i numbers
int[][][] dp = new int[2][k + 1][target + 1];
dp[0][0][0] = 1;
dp[1][0][0] = 1;
for(int i = 1; i <= A.length; i++){
for(int j = 1; j <= k; j++){
for(int v = 1; v <= target; v++){
// i has an offset of 1, becasue when i = 1
// we are actually referring to index 0
if(v >= A[i - 1]){
dp[i % 2][j][v] = dp[(i - 1) % 2][j][v] +
dp[(i - 1) % 2][j - 1][v - A[i - 1]];
} else {
dp[i % 2][j][v] = dp[(i - 1) % 2][j][v];
}
}
}
}
return dp[A.length % 2][k][target];
}
}
