算法D45 | 动态规划7 | 70. 爬楼梯 （进阶） 322. 零钱兑换 279.完全平方数

这道题目 爬楼梯之前我们做过，这次再用完全背包的思路来分析一遍 

代码随想录

Python:

翻译成背包问题，即：在容量为n的背包里，装入重量为1/2的物品，可以重复利用物品，所以是完全背包问题。由于顺序在结果中重要，所以是排列问题，所以先遍历背包，后遍历物品。

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[0] = 1
        for j in range(1,n+1):
            for i in [1, 2]:
                if j<i: continue
                dp[j] += dp[j-i]
        return dp[n]    

C++:

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<=2; i++) {
                if (j<i) continue;
                dp[j] += dp[j-i];
            }
        }
        return dp[n];
    }
};

322. 零钱兑换  

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

这句话结合本题 大家要好好理解。

视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换_哔哩哔哩_bilibili

代码随想录

Python二维:

第一遍推的，代码稍微冗余，逻辑差不多，模板还是模板啊。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount==0: return 0
        coins.sort(reverse=True)
        m = len(coins)
        dp = [[-1]*amount for _ in range(m+1)]
        for i in range(1, m+1):
            c = coins[i-1]
            for j in range(c-1, amount):
                if dp[i-1][j] != -1 and dp[i][j-c] != -1:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-c]+1)
                elif dp[i-1][j] != -1:
                    dp[i][j] = dp[i-1][j]
                elif dp[i][j-c] != -1:
                    dp[i][j] = dp[i][j-c] + 1
                elif (j+1) % c == 0:
                    dp[i][j] = (j+1)//c
        return dp[-1][-1]

Python一维：

优化成一维格式：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount+1)
        dp[0] = 0
        for c in coins:
            for j in range(c, amount+1):
                if dp[j-c]!=float('inf'):
                    dp[j] = min(dp[j-c]+1, dp[j])
        if dp[amount]==float('inf'): return -1
        return dp[amount]

C++一维:

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] = min(dp[j], dp[j-coins[i]]+1);
                }
            }
        }
        if (dp[amount]==INT_MAX) return -1;
        return dp[amount];
    }
};

279.完全平方数  

本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做 

视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数_哔哩哔哩_bilibili

代码随想录

Python:

和322类似的，把完全平方数当成硬币，放进大小为n的包里，硬币个数最少的方案。

class Solution:
    def numSquares(self, n: int) -> int:
        m = int(n**0.5)
        dp = list(range(n+1))
        for i in range(1, m+1):
            for j in range(i**2, n+1):
                dp[j] = min(dp[j-i**2]+1, dp[j])
        return dp[n]

C++:

优化一下卡哥的版本，遍历i到n的sqrt的int即可。

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, 0);
        for (int i=0; i<=n; i++) dp[i] = i;
        int m = int(sqrt(n));
        for (int i=1; i<=m; i++) {
            for (int j=i*i; j<=n; j++) {
                dp[j] = min(dp[j], dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
};