70. 爬楼梯

• 思路
  • example
  • 完全背包 + 排列
    • 背包外循环，物品（步数）内循环

求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];

• 复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n+1)
        dp[0] = 1
        m = 2
        for j in range(1, n+1): # 背包
            for i in range(1, m+1): # 物品
                if j >= i:
                    dp[j] += dp[j-i]
        return dp[n]

• 复习之前写法 (index i改为j更方便统一理解）

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

322. 零钱兑换

• 思路
  • example
  • 完全背包
    • 求最小的硬币个数，所以组合问题，排列问题都可以，不影响取最小值 (5+5+1=1+5+5=5+1+5)。这里按照 完全背包 + 组合 的思路来 （遍历：先物品，再背包）。
• 复杂度. 时间：O(n*amount), 空间: O(amount)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1 for _ in range(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)
        return dp[amount] if dp[amount] != amount+1 else -1

• 完全背包+排列 (2D)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins) 
        dp = [[amount+1 for _ in range(amount+1)] for _ in range(n+1)]
        dp[0][0] = 0
        for j in range(amount+1):
            for i in range(1, n+1):
                coin = coins[i-1]
                if j >= coin:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-coin]+1) # dp[i][j-coin]+1 !!!
                else:
                    dp[i][j] = dp[i-1][j] 
        return dp[n][amount] if dp[n][amount] != amount+1 else -1

279. 完全平方数

• 思路
  • example
  • 完全背包，最小数量：组合，排列均可。
• 复杂度. 时间：O(?), 空间: O(?)
  • 先背包，再物品 (完全背包+排列）

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf') for _ in range(n+1)]
        dp[0] = 0
        for j in range(1, n+1): # 背包
            i = 1
            while j >= i*i: # 物品
                dp[j] = min(dp[j], dp[j-i*i] + 1)
                i += 1
        return dp[n] 

• 先物品，再背包 (完全背包+组合）

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [n+1 for _ in range(n+1)]
        dp[0] = 0 # !!!
        for num in range(1, n+1):
            if num**2 > n:
                break 
            for j in range(num**2, n+1):
                dp[j] = min(dp[j], dp[j-num**2]+1)
        return dp[n]