Day45【动态规划】70.爬楼梯、322.零钱兑换、279.完全平方数网站首页 技术教程

Day45【动态规划】70.爬楼梯、322.零钱兑换、279.完全平方数

林沐华 2024-06-17 11:19:19

简介Day45【动态规划】70.爬楼梯、322.零钱兑换、279.完全平方数

70.爬楼梯

力扣题目链接/文章讲解

本题之前做过，这次尝试对这道题进行拓展

题目改为：一步一个台阶，两个台阶，三个台阶，.......，直到 i 个台阶。问有多少种不同的方法可以爬到楼顶呢？

和 377.组合总和 Ⅳ 进行对比

组合总和中是求和为目标的排列的个数，这道题是求爬到楼顶的方法数
化为背包问题：1 阶，2 阶，......， i 阶就是物品，楼顶阶数就是背包
每一阶可以重复使用，例如跳了 1 阶，还可以继续跳 1 阶，即相当于物品能够重复取
1、2 步和 2、1 步都是上三个台阶，但是这两种方法不一样，故也需要考虑顺序

同样，这道题不按照完全背包的最原始思路去想了，直接动态规划五部曲，和 377.组合总和 Ⅳ 是一模一样的

1、确定dp数组下标及值的含义

dp[j]：下标 j 表示爬到有 j 个台阶的楼顶，值表示有 dp[j] 种方法

2、确定递推公式

考虑怎么跳到第 j 个台阶的。可能是从第 j - 1 阶直接跳 1 阶到的第 j 个台阶，可能是从第 j - 2 阶直接跳 2 阶到的第 j 个台阶，可能是从第 j - 3 阶直接跳 3 阶到的第 j 个台阶......，可能是从第 j - m 阶直接跳 i 阶到的第 j 个台阶。dp[j] 代表的是方法数，需要把这些方法相加。故 dp[j] = dp[j-1] + dp[j-2] +......+dp[j - i]，即 dp[j] += dp[j - i]（遍历所有 i 并将结果累加）

(又出现了！求方案数的递推公式是 dp[j] += dp[j - w[i]])

3、dp 数组初始化

dp[0] 指的是爬到台阶 0 的方法数，为 1

其他位置初始化为 0，便于后面累加

4、确定遍历顺序

因为 dp[j] 的值依赖于其左边的 dp 值，从左向右遍历，保证待求位置的左边的 dp 值为更新过的正确值

5、打印 dp 数组验证

代码如下

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int j = 1; j <= n; j++) { // 从左向右遍历填充（遍历背包）
            for (int i = 1; i <= m; i++) { // 计算dp[j]时，需要计算所有dp[j-i]的和（遍历物品）
                if (j - i >= 0) dp[j] += dp[j - i];    // 前提是j>=i
            }
        }
        return dp[n];
    }
};

322.零钱兑换

力扣题目链接/文章讲解

视频讲解

先自己做了一下，用的完完全全的完全背包二维 dp 思路

amount视为背包容量
coins视为物品
求的是物品装满背包所需要的最少物品个数

每个物品可以无限放，是个完全背包问题

推导递推公式时，考虑：不需要放入物品 i 装满背包（dp[i - 1][j]），以及至少放入一个物品 i 装满背包（dp[i][j - w[i]] + 1，其中：[j - w[i]] 及 +1 保证了至少放入一个 i，dp第一维的 i 表示放入一个 i 后，还能继续选择 i 多次放入）两种情况

详细见代码注释

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // dp[i][j]: 从物品0到i任取，装满容量为j的背包，最少需要多少物品
        vector<vector<int> > dp(coins.size(), vector<int>(amount + 1));

        // 递推公式
        // 考虑不需要装入物品i的装满情况，则最少需要的物品个数为dp[i-1][j]
        // 考虑需要装入至少一件物品i的装满情况，则最少需要的物品个数为dp[i][j-weight[i]]+1
        // dp[i][j]应该为两种情况下的最小值，即dp[i][j]=min(dp[i-1][j], dp[i][j-weight[i]]+1)
        
        // 初始化：初始化dp数组的第一行和第一列
        for (int j = 0; j <= amount; ++j) { // 第一行：用物品0装满容量为j的背包，最少需要多少个。如果不能装满，后面需要用到min，为了不覆盖，置为一个很大的数
            if (j % coins[0] == 0)  // 能装满
                dp[0][j] = j / coins[0];
            else    // 不能装满
                dp[0][j] = INT_MAX - 1;
        }
        for (int i = 0; i < coins.size(); ++i) {    // 第一列：用物品i装满容量为0的背包，最少需要0个就能装满
            dp[i][0] = 0;
        }

        for (int i = 1; i < coins.size(); ++i)
            for (int j = 1; j <= amount; ++j) {
                if (j >= coins[i])
                    dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]] + 1);
                else
                    dp[i][j] = dp[i-1][j];
            }
        if (dp[coins.size() - 1][amount] == INT_MAX - 1) return -1;    // 注意这里的逻辑
        return dp[coins.size() - 1][amount];
    }
};

仍然能够用滚动数组优化，思考的时候想清楚滚动数组是如何对应二维数组的就行了

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // dp[j]：用物品装满容量为j的背包，最少需要多少物品
        vector<int> dp(amount + 1);

        // 二维的递推公式
        // 考虑不需要装入物品i的装满情况，则最少需要的物品个数为dp[i-1][j]
        // 考虑需要装入至少一件物品i的装满情况，则最少需要的物品个数为dp[i][j-weight[i]]+1
        // dp[i][j]应该为两种情况下的最小值，即dp[i][j]=min(dp[i-1][j], dp[i][j-weight[i]]+1)
        // 优化为一维则是：dp[j] = min(dp[j], dp[j-weight[i]]+1)，min中的第一项对应二维dp中的上一行，第二项对应二维dp中的本行左侧

        // 初始化：初始化二维dp数组的第一行
        for (int j = 0; j <= amount; ++j) { // 第一行：用物品0装满容量为j的背包，最少需要多少个。如果不能装满，后面需要用到min，为了不覆盖，置为一个很大的数
            if (j % coins[0] == 0)  // 能装满
                dp[j] = j / coins[0];
            else    // 不能装满
                dp[j] = INT_MAX - 1;
        }
        // 初始化：初始化二维dp数组的第一列，即滚动数组的首个元素，始终为0，表示装满容量为0的背包最少需要0个物品
        dp[0] = 0;

        for (int i = 1; i < coins.size(); ++i)  // 一行一行遍历填充（二维中）
            for (int j = 1; j <= amount; ++j) { // 每行从左向右遍历填充（二维中），第一列不用更新
                if (j >= coins[i])  // 如果能放下物品 i
                    dp[j] = min(dp[j], dp[j-coins[i]] + 1);
                // else
                //     dp[j] = dp[j];
            }
        if (dp[amount] == INT_MAX - 1) return -1;
        return dp[amount];
    }
};

滚动数组的推导很复杂是吧？能不能不用背包问题的原始思路，换种角度直接动态规划五部曲呢？当然是可以的！（之前其实用过了，只是在这道题我们对比一下原始思路与直接动态规划五部曲）

1、确定dp数组下标及值的含义

dp[j]：凑足总额为 j 所需钱币的最少个数为 dp[j]

2、确定递推公式

凑足总额为 j - coins[i] 的最少个数为 dp[j - coins[i]]，那么只需要加上一个钱币 coins[i] 即 dp[j - coins[i]] + 1 就是 dp[j]（考虑 coins[i] ）

所以 dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j])

3、dp数组如何初始化

首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0

其他下标对应的数值呢？

考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

所以下标非0的元素都是应该是最大值

4、确定遍历顺序：外层从左往右遍历背包容量，填充每个 dp[j] 时内层还需要一个 for 循环

5、打印 dp 数组验证

代码如下

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX - 1);
        dp[0] = 0;
        for (int j = 1; j <= amount; j++) {  // 遍历背包
            for (int i = 0; i < coins.size(); i++) { // 计算dp[j]时，需要计算所有dp[j-coins[i]]的最小值
                if (j - coins[i] >= 0) {
                    dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                }
            }
        }
        if (dp[amount] == INT_MAX - 1) return -1;
        return dp[amount];
    }
};

是不是简单了很多？

279.完全平方数

力扣题目链接/文章讲解

视频讲解

先自己做了一下，用的完完全全的完全背包二维 dp 思路

和 n 视为背包容量
数视为物品，数的平方就是 weight
求的是物品装满背包所需要的最少物品个数

每个物品可以无限放，是个完全背包问题

推导递推公式时，考虑：不需要放入物品 i 装满背包，以及至少放入一个物品 i 装满背包两种情况

详细见代码注释

class Solution {
public:
    int numSquares(int n) {
        // 背包容量：n
        // 物品：1,2,3,……,sqrt(n),物品重量为物品索引的平方
        // 物品1-sqrt(n)装满背包，所需要最少的物品数量

        // dp[i][j]:物品1到i放入容量为j的背包，dp[i][j]的值为最少的放入物品数量
        vector<vector<int> > dp(sqrt(n) + 1, vector<int>(n + 1));

        // 递推公式：dp[i][j] = min(dp[i-1][j], dp[i][j-weight[i]]+1)，考虑不放物品i和至少放一件物品i的情况，取最小值
        // 初始化第一行
        for (int j = 0; j <= n; ++j) {  // 物品1（重量为1）放入容量为j的背包，最少需要的物品个数
            if (j == 0) dp[1][j] = 0;   // 背包容量为0，最少需要0个
            else dp[1][j] = j;          // 背包容量为j，需要j个重量为1的物品
        }
        // 初始化第一列
        for (int i = 1; i <= sqrt(n); ++i) {
            dp[i][0] = 0;   // 放进容量为0的背包，最少需要0个物品即可装满
        }

        for (int i = 2; i <= sqrt(n); ++i)  // 遍历物品，一层一层遍历
            for (int j = 1; j <= n; ++j) {  // 遍历每层中的元素
                if (j >= i * i) // 如果容量j能装下物品i
                    dp[i][j] = min(dp[i-1][j], dp[i][j-i*i]+1);
                else
                    dp[i][j] = dp[i-1][j];
            }
        return dp[sqrt(n)][n];
    }
};

滚动数组如下

class Solution {
public:
    int numSquares(int n) {
        // 背包容量：n
        // 物品：1,2,3,……,sqrt(n),物品重量为物品索引的平方
        // 物品1-sqrt(n)装满背包，所需要最少的物品数量

        // dp[j]:物品放入容量为j的背包，dp[j]的值为最少的放入物品数量
        vector<int> dp(n + 1);

        // 递推公式：dp[j] = min(dp[j], dp[j-weight[i]]+1)，考虑不放物品i和至少放一件物品i的情况，取最小值
        // 初始化原二维dp第一行
        for (int j = 0; j <= n; ++j) {  // 物品1（重量为1）放入容量为j的背包，最少需要的物品个数
            if (j == 0) dp[j] = 0;   // 背包容量为0，最少需要0个
            else dp[j] = j;          // 背包容量为j，需要j个重量为1的物品
        }
        // 初始化第一列，物品放入容量为j的背包，需要的最少物品个数始终为0
        // dp[0] = 0;

        for (int i = 2; i * i <= n; ++i)  // 遍历物品，一层一层遍历
            for (int j = 1; j <= n; ++j) {  // 遍历每层中的元素，最左边元素为第一列的值始终为0，不用更新
                if (j >= i * i) // 如果容量j能装下物品i
                    dp[j] = min(dp[j], dp[j-i*i]+1);
                // else
                //     dp[j] = dp[j];
            }
        return dp[n];
    }
};

当然，类似上一道题，也有从另一个角度分析推导的，在文章讲解中有，这里不再赘述