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 int backPack(int m, int[] A) {
        // write your code here
        boolean[][] dp = new boolean[A.length+1][m+1];
        for(int i = 0; i <= A.length; i++) dp[i][0] = true;
        int ans =0;
        for(int i=1;i<=A.length;i++)
            for(int j=1;j<=m;j++){
                dp[i][j] = dp[i-1][j];
                if(j>=A[i-1]) dp[i][j] = dp[i][j] || dp[i-1][j-A[i-1]];
                if(dp[i][j]&&j>ans) ans = j;
            }
        return ans;
    }

考虑到我们只需要存最多两行的结果，滚动数组优化就显而易见了。

其实在背包九讲里面也有写过只存一行， 新一行的结果每次从右往左扫的，更经济些。简易程度上我还是更喜欢用取 mod 的滚动数组写法。

Backpack II

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

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

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

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

同时因为每次新迭代循环中， i 是不会走回头路的，所以状态与状态之间可以在不违反题意的情况下衔接起来

    public int backPackII(int m, int[] A, int V[]) {
        // write your code here
        int[][] dp = new int[A.length+1][m+1];

        int ans = 0;
        for(int i=1;i<=A.length;i++){
            for(int j=1;j<=m;j++){
                dp[i][j] = dp[i-1][j];
                if(j-A[i-1]>=0)
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-A[i-1]]+V[i-1]);
            }
        }
        return dp[A.length][m];
    }

在这里把两个for循环颠倒也是可以的, 等于一个是从上往下dp, 颠倒后是从左往右dp, 不影响运算结果

Perfect Squares

仔细观察一下这题:

• 数字n依赖数字n-1, 最坏情况f(n) = f(n-1)+1;

• 我们要凑出来一个和正好是 n 的选择组合；

• 能选的元素是固定数量的 perfect square (有的会超)

• 一个元素可以选多次；

这就是背包啊！

    public int numSquares(int n) {
        int x = (int)Math.sqrt(n);
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE); dp[0]= 0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=x;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 一个维度就可以了，但是循环依然是两层。

• 数组初始化为maxvalue时, dp[i]+1可能溢出, 导致最小值

比较直观的写法是这样(内外循环的顺序无所谓，但是最好从 amount 那个维度开始)

   public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE); dp[0]=0;
        for(int i=1;i<=amount;i++)
            for(int j=0;j<coins.length;j++){
                if(i>=coins[j] && dp[i-coins[j]]!=Integer.MAX_VALUE){
                    dp[i] = Math.min(dp[i], dp[i-coins[j]]+1);
                }
            }
        return dp[amount]==Integer.MAX_VALUE?-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];
    }
}

bottom up

    public int combinationSum4(int[] nums, int target) {
        // dp[i] = dp[i-nums[0]] + ...+ dp[i-nums[end];
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i=0;i<=target;i++){
            for(int num : nums){
                if(i+num<=target)
                    dp[i+num] += dp[i];
            }
        }
        return dp[target];
    }

K sum

背包类问题的扩展版本~

我们关注的维度有三个：

• 前 i 个元素，因为一个元素只能选一次；

• 选了 j 个元素，因为我们要求选 k 个数；

• 总和 sum，用于每次试图添加新元素时用来查询。

时间：O(len * k * target)，三重循环

空间：O(k * target)

public int kSum(int A[], int k, int target) {
        // write your code here
        int[][][] dp = new int[A.length+1][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 t=1;t<=target;t++)
                {

                    if(t>=A[i-1])
                        dp[i%2][j][t] = dp[(i-1)%2][j][t] +dp[(i-1)%2][j-1][t-A[i-1]];
                    else
                        dp[i%2][j][t] = dp[(i-1)%2][j][t];//don't select
                }

        return dp[A.length%2][k][target];
    }

Ones and Zeroes

研究了一下，发现是个背包。每个物品只有1个，占‘0’ ‘1’两种资源。一共资源有‘0’，‘1’两种资源。因为每个物品只能用一次，感觉dp不太好写。写了dfs，18个test cases后超时。top down approach应该没有重复子问题才对。

public class Solution {
    int maxCount = 0;
    public int findMaxForm(String[] strs, int m, int n) {
        dfs(strs, 0, 0, m, n);
        return maxCount;
    }

    public void dfs(String[] strs, int start, int curCount, int m, int n){
        if(start>strs.length||m<0||n<0)
            return;
        maxCount = Math.max(curCount, maxCount);
        for(int i=start;i<strs.length;i++){
            int[] digits = getCount(strs[i]);
            dfs(strs, i+1, curCount+1, m-digits[0], n-digits[1]);
        }
    }

    public int[] getCount(String s){
        char[] arr = s.toCharArray();
        int[] ans = new int[2];
        for(char c:arr){
            if(c=='0') ans[0]++;
            else ans[1]++;
        }
        return ans;
    }
}

这道题dp最重要的是要解决overcounting的问题。这也是一开始我尝试用dp没成功的地方。传统的dp都是从左上到右下，枚举的物品放在最内层循环。这样的话在计算max(dp[i][j], dp[i - numZeroes][j - numOnes] + 1时无法知道上一步用了哪个string，所以会存在overcounting。

正确的解锁方式是：

• 枚举物品string放在最外层

• 计算dp矩阵的时候从右下到左上，dp状态转移矩阵不变。这样保证了用的重复子问题结果没有使用当前的string，解决了overcounting的问题。

public class Solution {
    int maxCount = 0;
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for(String s : strs){
            int[] count = getCount(s);
            for(int i=m;i>=count[0];i--)
                for(int j=n;j>=count[1];j--){
                    dp[i][j]= Math.max(dp[i][j], dp[i-count[0]][j-count[1]]+1);
                }
        }
        return dp[m][n];
    }

    public int[] getCount(String s){
        char[] arr = s.toCharArray();
        int[] ans = new int[2];
        for(char c:arr){
            if(c=='0') ans[0]++;
            else ans[1]++;
        }
        return ans;
    }
}