代码随想录算法训练营第45天 |70. 爬楼梯（进阶）、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则直接跳过

确定dp数组以及下标的含义
- dp[j]的定义为：兑换总金额j需要最少的硬币数量
确定递推公式
- 状态转移方程为dp[j] = min(dp[j], dp[j - coins[i]] + 1);

dp数组如何初始化

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] = 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）

思路:

使用动态规划

确定dp数组以及下标的含义
- dp[j]的定义为：相加为j的完全平方数的最小数量

确定递推公式

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

dp数组如何初始化

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);
        }
    }
}

我的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];
    }
};