70. 爬楼梯 （进阶）
1、使用 01 背包解法
class Solution:
def climbStairs(self, n: int) -> int:
# dp 数组代表爬上第 i 阶有 dp[j] 种方法
dp = [0] * (n + 1)
dp[0] = 1
m = 2
# 排列先背包后物品
for i in range(n+1):
for j in range(1, m + 1):
if i >= j:
dp[i] += dp[i-j]
return dp[n]
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
if dp[i - coin] != float('inf'):
dp[i] = min(dp[i], dp[i - coin] + 1)
if dp[amount] == float('inf'):
return -1
return dp[amount]
class Solution:
def numSquares(self, n: int) -> int:
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(1, int(n ** 0.5) + 1):
for j in range(i * i, n + 1):
dp[j] = min(dp[j], dp[j - i * i] + 1)
return dp[n]