8/2，背包问题

挺经典的 dp 问题，就是不知道为啥 leetcode 上没有。

特点一：至少要用目标值作为一个 DP 维度

特点二：对具体元素敏感(比如 01 背包)，但对同一 totalSize / totalValue 来讲，有时候如何构造而来的具体路线不重要。这是由元素特性和背包 size 的约束条件决定的，也是有别于其他种类 DP 的一个重要区别。

比如 Combination Sum IV，就是典型的 “对最终结果敏感，对元素个数不敏感” 的问题，每次可以取任意元素，任意个，因此只用 dp[sum] 一个维度做 dp 就够了。

在只取 min/max 的时候我们不同的循环顺序都能保证正确答案；但是求解的数量时，要以 target value 为外循环。

Backpack

先从暴力搜索开始，结构图如下：

对于每个元素都会衍生出 (取/不取) 两种选择，所有可能的策略则是从最左面到最右面的一条 path，也即 binary tree 从 root 到 leaf node 的路径个数。

显然，路径个数 = 叶节点个数 = 2^n.

接下来的观察是关于题目性质的，可以发现我们最关注的是 “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;
    }
}

Backpack II

这次每个元素除了 size 之外也具有 value，就变成了更典型的 01 背包问题。

问题的结构依然具有 01 背包的性质，选一条 path 使得最终总价值最大，path 总数为 2^n. 同时对于同一个总的空间占用 totalSize 或者 totalValue，我们并不在乎它是怎么构造出来的，只要不重复选元素就行。

因此我们 dp 结构一致，而采用 int[][] 来记录

dp[i][j] 包里有 j 的空间，可以取前 i 个元素时，所能获得的最大收益。

同时因为每次新迭代循环中， 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];
    }
}

Perfect Squares

仔细观察一下这题:

• 我们要凑出来一个和正好是 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];
    }
}

Coin Change

背包类问题的马甲题。

• 每个元素可以取任意次；

• 只问最小的硬币数，就类似于 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];
    }
}

Backpack III

和背包 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];
    }
}

Combination Sum IV

原理和 climbing stairs 差不多，建一个大小等于 target + 1 的 array 代表多少种不同的方式跳上来，依次遍历即可。

时间复杂度 O(n * target)

注意这里内外循环的顺序不能错，要先按 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];
    }
}

K sum

背包类问题的扩展版本~

我们关注的维度有三个：

• 前 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];
    }
}