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

results matching ""

    No results matching ""