算法笔记_面试题_18.动态规划_模板及示例十几道(下)

目录

1. 背包问题

1.1 01背包

例14. 背包问题(二)_最多能装总共多大价值的物品

例15. 背包问题_最多能装总共多大尺寸的物品

例16. 整型数组是否可以分割成2个和相等子集

例17. 粉碎石头_最后一块石头的重量 II

例18. 数组元素添加+或-号,求构造目标和的方案总数_装满背包方案总数

其他01背包问题：（TODO）

1.2 完全背包

例19. 背包问题III_n种物品个数无限，最多能装总共多大价值的物品

例20. 零钱兑换II_硬币数量不限，凑成amount数量的方案总数

例21. 零钱兑换_硬币数量不限，凑成amount数量的最少硬币个数

续接文章   算法笔记_面试题_18.动态规划_模板及示例十几道(上)_惊鸿一博-CSDN博客

参考：九章算法 lintocde leetcode 代码随想录carl

1. 背包问题

背包问题分类：对于⾯试的话，其实掌握01背包，和完全背包，就够⽤了，最多可以再来⼀个多重背包。⽽完全背包⼜是也是01背包稍作变化⽽来，即：完全背包的物品数量是⽆限的。 所以背包问题的理论基础重中之重是01背包，⼀定要理解透！ leetcode上没有纯01背包的问题（lintcode上有），都是01背包应⽤⽅⾯的题⽬，也就是需要转化为01背包问题。

1.1 01背包 例14. 背包问题(二)_最多能装总共多大价值的物品

描述：有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.问最多能装入背包的总价值是多大?（A[i], V[i], n, m 均为整数, 你不能将物品进行切分, 你所挑选的要装入背包的物品的总大小不能超过m, 每个物品只能取一次）

（来源：lintcode 125 · 背包问题（二））

样例 1：

• 输入：
  • m = 10
  • A = [2, 3, 5, 7]
  • V = [1, 5, 2, 4]
• 输出：9
• 解释：装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9

样例 2：

• 输入：
  • m = 10
  • A = [2, 3, 8]
  • V = [2, 5, 8]
• 输出：10
• 解释：装入 A[0] 和 A[2] 可以得到最大价值, V[0] + V[2] = 10

代码

状态定义：因为涉及到选择物品的个数、总大小、总价值，3个变量，所以可以采用二维数组表示状态。dp[i][j]表示前i个物品中选择总大小为j的物品时的最大价值。(显然返回值是dp[n][m])

状态转移：看选择与不选择当前状态dp[i][j]中最后一个物品（最后一个物品大小A[i-1],价值为V[i-1], 不选择的状态为dp[i-1][..]）的最大价值是多少。分两种情况。

情况1：若当前总大小为j，j < A[i-i] （当前状态转移时的物品大小）时，只能从前i-1个物品中选择总大小为j的物品了，即 dp[i][j] = dp[i-1][j]。

情况2：若当前总大小 j >= A[i-1] , 则可以放入状态转移时的物品，这是看不选择i-1时的总价值 i-1的价值加上i-1的价值得 dp[i-1][j-A[i-1]] + V[i-1] ，同时对比 dp[i-1][j] （即使可能放下A[i-1]也先不放入）的总价值，取最小的。即 dp[i][j] = max (dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1]);

（为什么不从状态dp[i-1][j-1] 或者 dp[i][j-1]转移呢？因为j-1意味这需要有一个物品的大小恰好是1，才能转移到dp[i][j]，这种情况是特例而不是一般规律，所以那样写会很复杂）

初始化：dp[i][0] = ？; // 从前i个物品中选择总大小为j的物品，显然只能选0个，即最大价值为0。同理dp[0][j] = 0.

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int m, vector &A, vector &V) {
        // write your code here
        int n = A.size(); //物品的个数

        vector dp(n + 1, vector(m + 1)); // dp[i][j]表示前i个物品中选择总大小为j的物品时的最大价值
        
        //初始化
        dp[0][0] = 0;
        for (int i = 1; i < n + 1; i++) {
            dp[i][0] = 0; // 从前i个物品中选择总大小为j的物品，显然可以选0个，即最大价值为0。下一个for循环类似。
        }
        for (int j = 1; j < m + 1; j++) {
            dp[0][j] = 0;
        }

        //状态转移：相关状态dp[i-1][j] 以及 dp[i-1][j-A[i]]
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if (j < A[i-1]) { // 若状态转移时的物品(索引为i-1)大小大于当前总大小时，只能不选择该物品，
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = max (dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1]);
                }
            }
        }

        return dp[n][m];
    }
};

例15. 背包问题_最多能装总共多大尺寸的物品

描述: 在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为Ai.你不可以将物品进行切割。（来源：lintcode 92 · 背包问题）

样例 1：

• 输入：数组 = [3,4,8,5]  backpack size = 10
• 输出：9
• 解释：装4和5.

样例 2：

• 输入：数组 = [2,3,5,7]   backpack size = 12
• 输出：12
• 解释：装5和7.

代码1_二维数组

状态定义：还是可以定义成二维数组dp[i][j]表示 在前i个物体中选择，当背包容量为j时能装的最大值（即最大尺寸）。

状态转移：同上（例14）唯一区别：例14中 情况2：加的是价值，这里加的是尺寸大小。

即   dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]] + A[i-1] 如下所示，其它（如初始化）完全一样。

                if (j < A[i-1]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i-1]] + A[i-1]);
                }

代码2_一维数组（滚动数组）

上述方法，两层for循环显然时间复杂度O(nm), 空间复杂度O(nm), 其实可以优化。

根据上述状态转移方程，注意到 dp[i] 的状态只与 dp[i-1] 的状态有关，所以可以使用小状态赋值给大状态的方式，省去第一维的值，即只定义状态dp[j] (表示当背包容量为j时能装的最大值)，则状态转移方程变成了 dp[j] = max(dp[j], dp[j-A[i-1]] + A[i-1]); 其中i依然表示前i个物品。

接下来是遍历顺序的问题了，若是从容量0/1/2从小到到的遍历方式，则可能导致同一个物品被多次选择。而从大容量到小容量的遍历方式，则不会存在该问题（因为先计算大容量时的状态，再计算小容量时的状态，小容量的状态必然不会和大容量的状态有重合地放入同一个物品（放不下嘛！））所以，还是两层循环，先遍历物品，再遍历背包容量。代码如下（大同小异，注意这里初始化都为0，不太能对应上物理意义，但是为了保证计算上的正确性（取max了）就初始化为0）。

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    int backPack(int m, vector &A) {
        int n = A.size();
        vector dp(m + 1); //dp[j]表示当背包容量为j时，能装的最大值
        
        //初始化
        for (int j = 0; j < m + 1; j++) {
            dp[j] = 0;
        }
        
        for (int i = 1; i < n + 1; i++) {  // 物品遍历顺序从小到大（其实从大到小也一样）
            for (int j = m; j >= 0; j--) { // 特别注意：这里背包容量从大到小遍历
                if (j >= A[i-1]) {         // 该条件不能少！
                    dp[j] = max(dp[j], dp[j-A[i-1]] + A[i-1]); //状态转移方程少了一维，dp[j]被滚动赋值，称之为滚动数组喽
                }
            }
        }

        return dp[m];
    }
};

同理，例14也可以采用滚动数组的方式。状态转移方程是 dp[j] = max(dp[j], dp[j-A[i-1]] + V[i-1]); 其它都一样。

例16. 整型数组是否可以分割成2个和相等子集

描述：给你一个只包含正整数的非空数组nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 （来源 leetcode 416. 分割等和子集）

示例 1：

• 输入：nums = [1,5,11,5]
• 输出：true
• 解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

• 输入：nums = [1,2,3,5]
• 输出：false
• 解释：数组不能分割成两个元素和相等的子集。

代码

这道题是例15的应用（或者说是变型）。可以这样考虑，将数组的元素的值当做是物品的大小，子集当成是一个背包。若可以从所有物品中取出一部分，其大小正好等于该数组总和的一半（即这里定义的背包的大小），则剩余的必然也是数组总和的一半，则就可以此判断是否可以分割成2个和相等子集。所以：

• 背包大小的定义：m = sum/2,
• 物品个数：n = 数组的元素个数，
• 物品的大小：nums[i] 即数组元素大小。
• 判断目标：是否可以找到将物品装入背包的方案，使得 dp[sum/2] 等于 sum/2。

所以，代码与 例15 几乎一模一样，除了此题多了一个求 目标背包大小(sum/2) 和 最后的相等判断。

class Solution {
public:
    bool canPartition(vector& nums) {
        int n = nums.size(); //表示n个物品 // 数组中的元素表示每个物品的尺寸大小
        int sum = 0;
        
        for(auto num : nums) {
            sum += num;
        }
        if(sum % 2 == 1) { //特别注意：这个不要少了!!! 不然结果自然是不对的
            return false;
        }

        int m = sum/2; //表示背包大小 // 这个假设是巧妙的，选择一半物品若能正好装入背包dp[一半容量]=一半容量，则剩余的肯定也是一半，这就说明可以分成2个相等的子集了！
        vector dp(m + 1, 0); //状态 dp[j]表示 背包容量是j时能容纳的物品的最大大小 //根据状态定义初始化成0

        for (int i = 1; i < n + 1; i++) { //i表示前i个物品
            for (int j = m; j >= 0; j--) {
                if (j >= nums[i-1]) { //这句话可以合并到for循环中的循环条件
                    dp[j] = max(dp[j], dp[j-nums[i-1]] + nums[i-1]);
                }
            }
        }

        if (dp[m] == m) {
            return true;
        }
        return false;
    }
};

例17. 粉碎石头_最后一块石头的重量 II

描述： 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x = stones[i-1]; j--) { dp[j] = max(dp[j], dp[j-stones[i-1]] + stones[i-1]); } } return sum - 2 * dp[m]; } }; 例18. 数组元素添加+或-号,求构造目标和的方案总数_装满背包方案总数

描述：给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。(来源：leetcode 494. 目标和 ≈ lintcode 563 · 背包问题 V)

示例 1：

• 输入：nums = [1,1,1,1,1], target = 3  输出：5
• 解释：一共有 5 种方法让最终目标和为 3 。
  • -1 + 1 + 1 + 1 + 1 = 3
  • +1 - 1 + 1 + 1 + 1 = 3
  • +1 + 1 - 1 + 1 + 1 = 3
  • +1 + 1 + 1 - 1 + 1 = 3
  • +1 + 1 + 1 + 1 - 1 = 3

示例 2：

• 输入：nums = [1], target = 1  输出：1

代码及分析

这是一个装满01背包问题。

分析：即将数组中的数据分成2个子集，left 和 right, 使 left - right = target；又因为 left + right = sum(已知)， 则 2 * left = sum + target, 所以 left = (sum + target)/2；所以，相等于求 在数组nums中找到子集和为left值的方案有多少种（类似例题 组合总和-39题）。将 nums中的元素当做物品， left的值当做背包的容量，则这是一个01背包问题，变成求"装满背包"的方案总数有多少种。

状态定义：dp[j] 装满 j 容量的方案有dp[j]种

状态转移：当前状态dp[j], 则怎么从上一状态转移到当前状态呢，上一状态dp[j-1]显然不合适，因为物品的尺寸不一定就正好是1，所以考虑从dp[j-nums[i]]转移，即当装满j-nums[i]容量时（根据定义，对应方案总数dp[j-nums[i]]），再状态物品i的大小nums[i]，就状态了当前状态dp[j], 即 此时dp[j] = dp[j-nums[i]],  因为有很多个物品nums[i]，所以，举例子在能装下的条件 j >= nums[i]下：

• case1:先装满 j-num[0]容量，再装入物品num[0]，此时装满j的方案数 d[j] = dp[j-num[0]];
• case2:先装满 j-num[1]容量，再装入物品num[1]，此时装满j的方案数 d[j] = dp[j-num[1]];
• ...
• casei:先装满 j-num[i]容量，再装入物品num[i]，此时装满j的方案数 d[j] = dp[j-num[i]];

所有上述情况公共构成了装满j容量的方案，所以，在for循环中叠加： dp[j]=dp[j-num[0]] + dp[j-num[1]] + dp[j-num[2]] + ...

所以： dp[j] += dp[j-num[i]];

初始化：dp[0] = 1;  其他初始化为0. //特别注意：这里是根据计算需要，同时根据状态的定义也成立（容量为0的选择方案有1种，即选择0件物品）

class Solution {
public:
    int findTargetSumWays(vector& nums, int target) {
        int sum = 0;
        for (auto num : nums) {
            sum += num;
        }

        //两种无解的情况，直接返回0
        if (abs(sum) < abs(target)) { //注意：全部加起来或者取负也没有target大，则不存在这样的方案
            return 0;
        }
        if ((sum + target) % 2 == 1) { //等式中 2*left = sum + target,它们都是整数, 所以 sum + target 必须是偶数才存在解
            return 0;
        }

        int m = (sum + target) / 2; //背包容量
        int n = nums.size();
        vector dp(m + 1, 0); //状态dp[j]含义：装满j容量的方案有dp[j]种

        dp[0] = 1; //特别注意：这里计算需要，同时根据状态的定义也成立（容量为0的选择方案有1种，即选择0件物品）
        
        for (int i = 1; i < n + 1; i++) { // i表示装入前i个物品（i从0开始也可，表示当装入第i个物品时）
            for (int j = m; j >= nums[i-1]; j--) { //特别注意：容量从最大开始到小（小但至少要能放下当前物品）遍历！
                dp[j] += dp[j-nums[i-1]];
            }
        }

        return dp[m];        
    }
};

其他01背包问题：（TODO） 1.2 完全背包

class Solution {
public:
    int backPackIII(vector &A, vector &V, int m) {
        int n = A.size(); //物品种类数
        
        vector dp(m + 1, 0); //状态dp[i]表示当容量为i时，能装入背包的最大价值 //注意：根据状态定义暂初始化为0

        for (int i = 1; i < n + 1; i++) { // i：表示前i种物品
            for (int j = A[i-1]; j < m + 1; j++) { //注意：遍历顺序，背包容量从小到大，起始容量值至少要比当前物品大小要大。
                dp[j] = max(dp[j], dp[j-A[i-1]] + V[i-1]);
            }
        }

        return dp[m];
    }
};

class Solution {
public:
    int change(int amount, vector& coins) {
        int n = coins.size(); //硬币种类数
        vector dp(amount + 1, 0); //状态dp[j]表示当总金额为j时，能装入背包的最大金额 //注意：根据状态定义暂初始化为0
        
        dp[0] = 1; //特别注意：初始化总金额0有1种方案，即选择0个硬币
        
        for (int i = 1; i < n + 1; i++) { // i表示前i种硬币
            for (int j = coins[i-1]; j < amount + 1; j++) { // 注意：完全背包（物品个数无限时）问题，从小容量到大容量遍历
                dp[j] += dp[j-coins[i-1]];
            }
        }

        return dp[amount];
    }
};

class Solution {
public:
    int coinChange(vector& coins, int amount) {
        int n = coins.size();
        int max = amount + 1;
        vector dp(amount + 1, max); //状态dp[j]表示凑成j的金额需要的最少硬币个数。
        dp[0] = 0; //这个初始化不能忘

        for (int i = 1; i < n + 1; i++) {
            for (int j = coins[i-1]; j < amount + 1; j++) { //完全背包问题，从小到大遍历背包
                dp[j] = min(dp[j], dp[j-coins[i-1]] + 1); //可能存在凑不成amount的情况，这时dp[j]会等于max
            }
        }

        return (dp[amount] == max) ? -1 : dp[amount];
    }
};