随想录一刷Day45——动态规划

Day45_动态规划

22. 爬楼梯

70. 爬楼梯
思路：

利用完全背包的思想来考虑这题，有步长为1和步长为2这两种物品，可以多次选择

1. dp[i]表示走到第 i 层楼梯的方法数
2. dp[i] += dp[i - j] j == 1 || j == 2，物品只有两个
3. 初始化 dp[0] = 1
4. 遍历顺序，由于如果要到达第 3 级楼梯，先走1再走2和先走2再走1是不一样的，所以此处求的是排列，物品放在内层循环。

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= 2; j++) {
                if (i >= j) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

23. 零钱兑换

322. 零钱兑换
思路：

本题要求最少硬币数量

1. dp[j] 表示凑成金额 i 所需要的最少硬币数
2. dp[j] = min(dp[j], dp[j - coins[i]] + 1)，可以看到这里没有重复累加，不涉及到排列组合的问题
3. 初始化 dp[0] = 0 金额为 0 需要 0 个硬币，由于要求最小，所以初始化为一个最大值
4. 不涉及排列组合，顺序可以随意

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int coins_size = coins.size();
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int j = 0; j <= amount; j++) {
            for (int i = 0; i < coins_size; i++) {
                if (j >= coins[i] && dp[j - coins[i]] != INT_MAX) {
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

24. 完全平方数

279. 完全平方数
思路：

又是一个完全背包，每个元素（完全平方数）的大小为其值，价值为种类数 +1

1. dp[j] 表示凑成 j 的最少种类数
2. dp[j] = min(dp[j], dp[j - pow_num[i]] + 1) 这里还是不涉及排列组合
3. 初始化 dp[0] = 0 ，初始化其他部分为 INT_MAX
4. 不涉及排列组合无所谓排列顺序

class Solution {
public:
    int numSquares(int n) {
        int k = (int)sqrt(n); // 平方数基数的上限
        vector<int> pow_num(k + 1, 0);
        for (int i = 1; i <= k; ++i) pow_num[i] = i * i; // 生成所有可能用到的平方数
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= k; i++) {
            for (int j = pow_num[i]; j <= n; j++) {
                dp[j] = min(dp[j], dp[j - pow_num[i]] + 1);
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16