代码随想录算法训练营第四十五天 | 动态规划 part 7 | 70. 爬楼梯 （进阶）、322. 零钱兑换、279.完全平方数

70. 爬楼梯 （进阶）

Leetcode

思路

这道题如果题目改成可以一次爬1阶，2阶，3阶…m阶的话，将会是一个求排列的完全背包问题。

背包容量等于台阶，一次性爬台阶的数相当于物品，求装满背包的排列方式。

代码

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[0] = 1

        for i in range(1, n + 1):
            for j in range(1, 3):
                if i - j >= 0:
                    dp[i] += dp[i - j]

        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11

• 时间复杂度: O(nm)
• 空间复杂度: O(n)

代码中m表示最多可以爬m个台阶，代码中把m改成2就是本题70.爬楼梯可以AC的代码了。

322. 零钱兑换

Leetcode

思路

本题是完全背包的题。求装满背包的最小物品个数。

1. dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
2. 递推公式：dp[j] = min(dp[j], dp[j - coin])
3. 初始化：因为是求最小值，所以dp初始化的时候全部设定为最大值float('inf')。对于dp[0]，需要设置为0。因为凑齐0元需要0个硬币。
4. 遍历顺序：无所谓，因为排列和组合都不影响钱币的最小个数

代码

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        dp = [float("inf")] * (amount + 1)
        dp[0] = 0
        for coin in coins:
            for j in range(coin,amount + 1):
                dp[j] = min(dp[j], dp[j - coin] + 1)
        
        if dp[-1] == float('inf'):
            return -1
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12

• 时间复杂度: O(n * amount)，其中 n 为 coins 的长度
• 空间复杂度: O(amount)

279.完全平方数

Leetcode

思路

和上一题一样的完全背包求装满背包的最小物品个数。

完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

代码

class Solution:
    def numSquares(self, n: int) -> int:
    	# 因为n最大是10^4
        nums = [i**2 for i in range(1, 101)]

        dp = [float("inf")] * (n + 1)
        dp[0] = 0
        for num in nums:
            for j in range(num, n + 1):
            	#可以选择这个物品，也可以不选择
                dp[j] = min(dp[j], dp[j - num] + 1)

        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13

• 时间复杂度: O(n * √n)
• 空间复杂度: O(n)