刷题笔记之动态规划(二)

在动态规划(一)中我已经列出了动态规划五部曲，这里不再赘述，本篇博客主要总结动态规划中的背包问腿。

0-1背包

理论基础

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
举个简单的例子：
背包的最大重量为4。
物品为：

物品	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最大价值是多少？

二维dp数组01背包

动态规划五部曲：

确定dp数组以及下标的含义
do[i][j]: 从下标为[0-i]的物品中任取，放进容量为j的背包，价值总和为dp[i][j]
确定递推公式
两种情况：
1.不放物品i：dp[i][j] = dp[i - 1][j];
由上式推出，背包容量为j，不放物品i的价值就是dp[i - 1][j]
2.放入物品i： dp[i][j] = dp[i - 1][j - weight[i]] + value[i];
与不放物品i不同的是，此时背包容量已经减去了物品i的重量，即j - weight[i]，那当然要把物品i的价值value[i]加上，别忘了dp[i][j]的含义始终是价值。
所以递推公式：
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
dp数组初始化
从对dp[i][j]的定义出发，如果背包容量j为0，即dp[i][0]，无论取多少物品，背包价值一定为0，如图：

由状态转移方程可知，i由i - 1推导而来，所以i = 0的时候一要初始化。
当只放入物品0，即dp[0][j]：
如果j < weight[i]，即背包容量小于物品0重量时，dp[0][j] = 0;
如果j >= weight[i]，那么dp[0][j] = value[0],如图：
dp数组结果
初始化代码如下：

1
2
3

for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

那其他位置需要初始化吗？
其实不用，从状态转移方程可以看出:dp[i][j]是由其左上方数值推导而来，就算初始化了也会被覆盖，为了方便初始化为0即可。

确定遍历顺序
显然背包问题有两个维度，物品和背包重量。那么该先遍历物品还是先遍历背包呢？
如果采用二维数组，先遍历物品还是先遍历背包都是可行的。因为dp[i][j]都是由其左上方(包括正上方)得来，就算颠倒顺序，也不会印象dp数组的推导。

//先遍历物品
for (int i = 1; i < weight.length; i++) { // 遍历物品
    for (int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else 
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}
//先遍历背包
    for (int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for (int i = 1; i < weight.length; i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

打印dp数组

要求的结果为**dp[2][4]**。

一维dp数组01背包

在使用二维数组时，递推公式为：dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
如果把dp[i - 1]拷贝到dp[i]上，上式可变为：dp[i][j] = Math.max(dp[i][j], dp[i][j - weight[i]] + value[i]);
既然dp[i]可以原封不动的拷贝下来，那不如直接舍弃dp[i]，用个一维数数组:
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

动态规划五部曲：

确定dp数组以及下标的含义
dp[j]: 容量为j的背包，所装的最大价值为dp[j]
确定递推公式
两种情况：
1.不放物品i：dp[j] = dp[j];
即二维数组中的dp[i][j] = dp[i - 1][j];
2.放入物品i：dp[j] = dp[j - weight[i]] + value[i];
即二维数组中的：dp[i][j] = [i - 1][j - weight[i]] + value[i];
所以递推公式：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
dp数组初始化
首先是dp[0],容量为0的背包能装下物品的最大价值当然是0。那么非0下标如何初始化呢？
从递推公式可以看出，dp[j]每次都要在dp[j]与dp[j - weight[i]] + value[i]取最大值，如果给非0下标定义一个比较大的值，就有可能覆盖掉正确的值，那索性就初始化为0即可。
1
2
dp[0] = 0;
dp[1] = 0;

确定遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

首先我们发现遍历背包时是倒序遍历，这样做是为了保证物品i只被放入一次。

物品	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

举个例子，如果正序遍历：
dp[1] = dp[1 - weight[0]] + value[0] = 15;
dp[2] = dp[2 - weight[1]] + value[1] = 30;
dp[2] = 30意味着物品0被放入了两次。
再来看看倒序遍历:
dp[2] = dp[2 - weight[1]] + value[1] = 20;
dp[1] = dp[1 - weight[0]] + value[0] = 15;

那能不能像二维数组那样随意颠倒背包和物品的遍历顺序呢？
不能！如果先遍历背包，再遍历物品，每个背包就只会放入一个物品。

打印dp数组

要求的结果为**dp[4]**。

理论说完了，下面进入实战环节！

LeetCode 416. 分割等和子集

LeetCode题目链接
在做题之前有几个需要注意的点：

背包的体积为 sum / 2
背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
背包如果装满就说明找到了和为 sum / 2 的子集
背包中每一个元素不可重复放入

动态规划五部曲：

确定dp数组以及下标的含义
dp[j]: 容量为j的背包，能放入元素的和的最大值为dp[j]
确定递推公式
因为本题物品的价值和重量皆为nums[i],即：
dp[j] = Math.max(dp[j], dp[j - nums[j]] + nums[j]);
dp数组初始化
1
2
dp[0] = 0;//容量为0的背包，能放入元素的和的最大值为0
dp[1] = 0;
至于dp[1]为什么等于1，我在前面的一维数组01背包里已经详细解释过。

确定遍历顺序

for(int i = 1; i < nums.length; i++){//物品
    for(int j = target; j >= nums[i]; j--){//背包
        dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}

打印dp数组
nums = [1,5,11,5]，结果为：
0 1 1 1 1 5 6 6 6 6 10 11

完整代码

class Solution {
    public boolean canPartition(int[] nums) {
        if (nums.length == 1) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //总和为奇数，不能平分
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 1; i < nums.length; i++) {//物品
            //当j < nums[i]，即背包容量小于物品重量时就不需要再遍历了
            for (int j = target; j >= nums[i]; j--) {//背包
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }
}

LeetCode 1049. 最后一块石头的重量 II

LeetCode题目链接
在416. 分割等和子集中，只有将集合内元素完全平分才返回true,而本题是要将两堆石头尽可能平分，使其重量和最小，这就可以转化为一个01背包问题。

动态规划五部曲：

确定dp数组以及下标的含义
dp[j]: 容量为j的背包，可以背的最大重量为dp[j]
确定递推公式
石头的重量和价值都可以表示为stones[i],即：
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);

dp数组初始化

1 2	dp[0] = 0;//容量为0的背包，可以背的最大重量为0 dp[1] = 0;

确定遍历顺序

for(int i = 0; i < stones.length; i++){
    //当j < stones[i]，即背包容量小于物品重量时就不需要再遍历了
    for(int j = target; j >= stones[i]; j--){
        dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}

打印dp数组

dp[3]就是dp[target]，即一堆石头的重量，而就是另一堆sum - dp[target]，由于sum / 2是向下取整的，则有sum - dp[target] >= dp[target]，要求得两堆石头的重量差，用sum - dp[target] - dp[target]即可。

完整代码

class Solution {
    public int lastStoneWeightII(int[] stones) {
        if (stones.length == 0) {
            return 0;
        }
        int sum = 0;
        for (int i : stones) {
            sum += i;
        }
        //注意这里可能向下取整
        int target = sum / 2;
        int[] dp = new int[target + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        //dp[target]为一堆石头的最大重量，另一堆是sum - dp[target]
        int res = (sum - dp[target]) - dp[target];
        return res;
    }
}

LeetCode 494. 目标和

LeetCode题目链接

动态规划五部曲：

确定dp数组以及下标的含义
dp[j]: 装满容量为j的背包，有dp[j]种方法
确定递推公式
如果把正数记为集合P，负数记为集合Q，有：
sum(P) - sum(Q) = target
sum(P) + sum(Q) = sum(SUM)
sum(P) = (sum + target) / 2;
也就是说，我们只需要找到有多少种方法可以从数组中选出若干个元素使得它们的和等于(target + sum(nums)) / 2即可。这就变成了一个经典的01背包问题。
则状态转移方程为：dp[j] += dp[j - nums[i]];
为什么是dp[j] + dp[j - nums[i]]而不是取最大值？
依然分两种情况：
不放物品i：原来已经有多少种方案数就不变
放入物品i：剩下要组成和为j - nums[i] 的方案数就等于dp[j - nums[i]]
两种情况相加才是总的方案数。
dp数组初始化
1
dp[0] = 1;
如果让dp[0] = 0，那么后面的结果都是0！

确定遍历顺序

for(int i = 0; i < nums.length; i++){
    for(int j = pNum; j >= nums[i]; j--){
        dp[j] += dp[j - nums[i]];
    }
}

打印dp数组

完整代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        /*
        正数记为P,负数记为Q，有：
        sum(P) - sum(Q) = target
        sum(P) + sum(Q) = sum(SUM)
        sum(P) = (sum + target) / 2;
        */
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        //如果target过大 sum将无法满足
        if (target <= 0 && sum < -target) {
            return 0;
        }
        //如果target + sum不是偶数，也无法满足
        if ((target + sum) % 2 != 0) {
            return 0;
        }
        //正数P
        int pNum = (sum + target) / 2;
        int[] dp = new int[pNum + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = pNum; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[pNum];
    }
}

LeetCode 474. 一和零

LeetCode题目链接

这道题的种strs数组里的元素就是物品，每个物品只有一个，而m和n为背包，所以应该定义一个二维数组用来对应m和n两个维度。

动态规划五部曲：

确定dp数组以及下标的含义
dp[i][j]: 最多有i个0和j个1的strs的最大子集为dp[i][j]
确定递推公式
对应01背包的递推公式：dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
我们定义字符串中为0的字符为zeroNum,为1的定义为oneNum,则递推公式为：
dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
式中zeroNum和oneNum为物品的重量，而字符本身的个数为物品的价值。
dp数组初始化
1
dp[0][0] = 0;

确定遍历顺序

for(int i = m; i >= zeroNum; i--){
    for(int j = n; j >= oneNum; j--){
        dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
    }
}

为了得到zeroNum和oneNum的数量，我们还需要在每次循环前进行统计。

for(String str : strs){
    int zeroNum = 0, oneNum = 0;//统计一个字符串中0和1的数量
    for(int k = 0; k < str.length(); k++){
        if(str.charAt(k) == '0'){
            zeroNum++;
        }else{
            oneNum++;
        }
    }
    for(int i = m; i >= zeroNum; i--){
        for(int j = n; j >= oneNum; j--){
            dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
        }
    }
}

打印dp数组

完整代码

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            int zeroNum = 0, oneNum = 0;//统计一个字符串中0和1的数量
            for (int k = 0; k < str.length(); k++) {
                if (str.charAt(k) == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

完全背包

完全背包与0-1背包的唯一区别就是：每个物品可以取无限次。
在前面的一维数组0-1背包理论中我强调遍历顺序为先遍历物品再遍历背包，且遍历背包为倒序，这样做是为了保证物品i只被放入一次。

```java
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

在完全背包中，物品和背包的遍历顺序是可以调换的，且要把背包遍历变为正序，保证一个物品可以取无限次，直到背包装满。
但在有些题目中，先遍历物品再遍历背包是求组合数，先遍历背包再遍历物品是求排列数。这个我会在具体题目中详细分析。

LeetCode 518. 零钱兑换 II

LeetCode题目链接

动态规划五部曲：

确定dp数组以及下标的含义
dp[j]: 凑成总金额为j的硬币组合为dp[j]
确定递推公式
1
dp[j] += dp[j - coins[i]];
与494. 目标和一样，求装满背包有几种方法，统一都为这个公式。
dp数组初始化
1
dp[0] = 1;
这里dp[0]一定要定义为1,如果定义为0，那么后面将全为0。
如果从我们对dp数组的定义考虑，凑成总金额为0的硬币组合为1，也可以说凑成总金额为0的硬币组合为0，但题目描述中coins[i] >= 1，也就是说不会有硬币为0的情况，这里不必过多纠结，dp[0] = 1 仅仅是为了dp数组方便运算。
确定遍历顺序
对本题来说求的是组合数而不是排列数，以示例 1举例：
amount = 5, coins = [1, 2, 5]
[1,2,2]和[2,2,1]是相同的组合数，论排列数来说它们是不同的。
先来看先遍历物品，再遍历背包的情况:
1
2
3
4
5
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
dp[j] += dp[j - coins[i]];
}
}
coins[0] = 1, coins[1] = 2;那么组合中只有[1,2],而不会出现[2,1]。
再来看先遍历背包，再遍历物品：
1
2
3
4
5
for (int j = 0; j <= amount; j++) { // 遍历背包容量
for (int i = 0; i < coins.size(); i++) { // 遍历物品
if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
}
}
背包会依次装进coins[0]和coins[1]，即会出现[1,2]和[2,1]两种情况！这里的dp[j]算出来的就是排列数。

再说的通俗一点，先遍历物品，再遍历背包相当于把物品0全部遍历完后，不会再得到含有物品0的结果，因为此时已经开始遍历物品2。
而先遍历背包，再遍历物品相当于每当背包容量变大一次，就会把所有小于等于背包容量的物品再放入背包。

打印dp数组

完整代码

class Solution {
    public int change(int amount, int[] coins) {
        if (coins.length == 1) {
            if (amount % 2 != 0 && coins[0] % 2 == 0) {
                return 0;
            }
        }
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        //求组合数先遍历物品再遍历背包
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

LeetCode 377. 组合总和 Ⅳ

LeetCode题目链接
本题与518. 零钱兑换 II唯一的不同是求排列数，除了遍历顺序颠倒其他代码原封不动。

class Solution {
    //先物品再背包-组合数
    //先背包再物品-排列数
    public int combinationSum4(int[] nums, int target) {
        if (nums.length == 1) {
            if (nums[0] > target) {
                return 0;
            }
        }
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int j = 0; j <= target; j++) {
            for (int i = 0; i < nums.length; i++) {
                if (j >= nums[i]) {//背包容量大于物品重量才加
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }
}

LeetCode 322. 零钱兑换

LeetCode题目链接
 518. 零钱兑换 II是求有多少种方法能凑成价值为amount的货币，而本题求的是凑成价值amount最少需要多少个硬币。
coins = [1, 2, 5], amount = 11
[1,1,5]和[5,1,1]都可以凑成11，但我们求的不是排列或组合，而是数量！所以本题为纯背包问题，即物品和背包的遍历先后顺序可以调换。

动态规划五部曲：

确定dp数组以及下标的含义
dp[j]: 凑成价值为j最少硬币数量为dp[j]
确定递推公式
1
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1)
两种情况：
不放物品i: 数量就是dp[j]
放入物品i：背包容量要先减去它的重量j - coins[i],再加1记为放入了一个硬币，即dp[j - coins[i]] + 1
dp数组初始化
首先dp[0] = 0(凑成价值为0最少硬币数量为0),非0下标如何初始化呢？
从递推公式可以看出，我们要求最小值，为了不让我们初始化的值覆盖真实值，将它们全部初始化成最大值即可。
1
2
3
4
5
int max = Integer.MAX_VALUE;
for(int i = 0; i < dp.length; i++){//非0下标全初始化为最大值
dp[i] = max;
}
dp[0] = 0;

确定遍历顺序

//先遍历背包还是物品无所谓
for(int i = 0; i < coins.length; i++){
    for(int j = coins[i]; j <= amount; j++){
        //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
        if(dp[j - coins[i]] != max){
            dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
        }
    }
}

打印dp数组
coins = [1, 2, 5], amount = 11,结果为：
0 1 1 2 2 1

完整代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        int max = Integer.MAX_VALUE;
        for (int i = 0; i < dp.length; i++) {
            dp[i] = max;
        }
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (dp[j - coins[i]] != max) {
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }
}

LeetCode 279. 完全平方数

LeetCode题目链接
与322. 零钱兑换一样是求最少数量，做题步骤也大致相同，直接上代码！

    class Solution {
    public int numSquares(int n) {
        if (n == 1) {
            return 1;
        }
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = max;
        }
        dp[0] = 0;
        //i * i 代表平方数
        for (int i = 1; i * i <= n; i++) {
            for (int j = i * i; j <= n; j++) {
                if (dp[j - i * i] != max) {
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
                }
            }
        }
        return dp[n];
    }
}

LeetCode 139. 单词拆分

LeetCode题目链接
动态规划五部曲：

确定dp数组以及下标的含义
dp[i]: 能否在字典中找到组成长度为i的单词
确定递推公式
如果dp[j]为true,且在[j,i]这个区间里的字串出现在字典中，那么dp[i]就为true.(j < i)
1
2
3
if(set.contains(s.substring(j, i)) && dp[j]){
dp[i] = true;
}
dp数组初始化
1
dp[0] = true;
提示中有1 <= s.length <= 300，所以本来dp[0]就无意义，这里只是为了后续计算。

确定遍历顺序

//先遍历背包还是物品无所谓
for(int i = 1; i <= s.length(); i++){
    for(int j = 0; j < i && !dp[i]; j++){
        if(set.contains(s.substring(j, i)) && dp[j]){
            dp[i] = true;
        }
    }
}

打印dp数组
s = “leetcode”, wordDict = [“leet”, “code”],结果为：
1 0 0 0 1 0 0 0 1

完整代码

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i && !dp[i]; j++) {
                if (set.contains(s.substring(j, i)) && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}