代码随想录算法训练营第45天 |70. 爬楼梯 （进阶）、322. 零钱兑换、279.完全平方数

发布于 2023-03-02  317 次阅读

AI 摘要

本文介绍了算法训练营第45天学习的三个算法题目：70. 爬楼梯、322. 零钱兑换、279. 完全平方数。对每个问题都给出了思路、AC代码以及标准答案，并详细解释了DP算法的递推公式、dp数组的初始化、遍历顺序等问题。其中70. 爬楼梯和377. 组合总和 Ⅳ几乎一样，都是求排列的完全背包问题，而322. 零钱兑换是完全背包问题，而279. 完全平方数则是求最小值的背包问题。

70. 爬楼梯 - 力扣（Leetcode）

思路:

  • 和377. 组合总和 Ⅳ - 力扣（Leetcode）几乎一样，而且也是求排列的完全背包问题

    1. 确定dp数组以及下标的含义

      • dp[j]的定义为：到达j层台阶的方法数量

    2. 确定递推公式

      • 状态转移方程为dp[j] += dp[j - lt[i]];

    3. dp数组如何初始化

      vector<int> dp(n + 1, 0);

    4. 确定遍历顺序

      for(int j = 0; j <= n; ++j) {
    for(int i = 0; i < 2; ++i) {
        if(j >= lt[i]) {
            dp[j] += dp[j - lt[i]];
        }
    }
}

我的AC代码

// 时间复杂度O(2n),空间复杂度O(n)
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        int lt[2] = {1, 2};
        dp[0] = 1;
        for(int j = 0; j <= n; ++j) {
            for(int i = 0; i < 2; ++i) {
                if(j >= lt[i]) {
                    dp[j] += dp[j - lt[i]];
                }
            }
        }
        return dp[n];
    }
};

标准答案

// 时间复杂度O(2n),空间复杂度O(n)
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 >= 0) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};

322. 零钱兑换 - 力扣（Leetcode）

思路:

  • 因为本题钱币可以无限使用，所以是完全背包问题。因为求的是最小钱币数量所以递推公式是dp[j] = min(dp[j], dp[j - coins[i]] + 1);，又因为是求最小，所以要将所有非0下标初始化为INT_MAX,在状态转移之前要进行判断，若dp[j - coins[i]] == INT_MAX则直接跳过

    1. 确定dp数组以及下标的含义

      • dp[j]的定义为：兑换总金额j需要最少的硬币数量

    2. 确定递推公式

      • 状态转移方程为dp[j] = min(dp[j], dp[j - coins[i]] + 1);

    3. dp数组如何初始化

      vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;

    4. 确定遍历顺序

      for(int i = 0; i < coins.size(); ++i) {
    for(int j = coins[i]; j <= amount; ++j) {
        if(dp[j - coins[i]] != INT_MAX) {
            dp[j] = min(dp[j], dp[j - coins[i]] + 1);
        }
    }
}

我的AC代码

// 时间复杂度O(m x n),空间复杂度O(n)
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        if(amount == 0) return 0;
        for(int i = 0; i < coins.size(); ++i) {
            for(int j = coins[i]; j <= amount; ++j) {
                if(dp[j - coins[i]] != INT_MAX) {
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if(dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

标准答案

物品在外循环，背包在内循环

// 时间复杂度O(m x n),空间复杂度O(n)
// 版本一
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过
                    dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                }
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

背包在外循环，物品在内循环

// 时间复杂度O(m x n),空间复杂度O(n)
// 版本二
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {  // 遍历背包
            for (int j = 0; j < coins.size(); j++) { // 遍历物品
                if (i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX ) {
                    dp[i] = min(dp[i - coins[j]] + 1, dp[i]);
                }
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

279. 完全平方数 - 力扣（Leetcode）

思路:

  • 使用动态规划

    1. 确定dp数组以及下标的含义

      • dp[j]的定义为：相加为j的完全平方数的最小数量

    2. 确定递推公式

      // 状态转移方程
dp[j] = min(dp[j], dp[j - i * i] + 1);

    3. dp数组如何初始化

      vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;

    4. 确定遍历顺序

      for(int i = 1; i <= weightNum; ++i) {
    for(int j = i * i; j <= n; ++j) {
        if(dp[j - i * i] != INT_MAX) {
            dp[j] = min(dp[j], dp[j - i * i] + 1);
        }
    }
}

我的AC代码

// 时间复杂度O(m x n),空间复杂度O(n)
class Solution {
public:
    int numSquares(int n) {
        int weightNum = (int)(sqrt(n));
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 1; i <= weightNum; ++i) {
            for(int j = i * i; j <= n; ++j) {
                if(dp[j - i * i] != INT_MAX) {
                    dp[j] = min(dp[j], dp[j - i * i] + 1);
                }
            }
        }
        return dp[n];
    }
};

标准答案

先遍历物品再遍历背包

// 时间复杂度O(m x n),空间复杂度O(n)
// 版本一
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i * i <= n; i++) { // 遍历物品
            for (int j = i * i; j <= n; j++) { // 遍历背包
                dp[j] = min(dp[j - i * i] + 1, dp[j]);
            }
        }
        return dp[n];
    }
};

先遍历背包再遍历物品

// 时间复杂度O(m x n),空间复杂度O(n)
// 版本二
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) { // 遍历背包
            for (int j = 1; j * j <= i; j++) { // 遍历物品
                dp[i] = min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
};