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]
