509. 斐波那契数
1、动态规划
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
# dp[i] 代表第 i 个数的斐波那契值
dp = [0] * (n+1)
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[-1]
2、优化动态规划
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
# dp[i] 代表第 i 个数的斐波那契值,只需要记录前 2 个值
dp = [0, 1]
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
dp[0], dp[1] = dp[1], dp[0] + dp[1]
return dp[1]
70. 爬楼梯
方法一
class Solution:
def climbStairs(self, n: int) -> int:
if n < 2:
return n
# dp[i] 代表爬到第i阶的方法
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
方法二
class Solution:
def climbStairs(self, n: int) -> int:
if n < 2:
return n
# 只需要记录 2 个状态
dp = [1, 2]
for i in range(3, n+1):
dp[0], dp[1] = dp[1], dp[0] + dp[1]
return dp[1]
746. 使用最小花费爬楼梯
1、动规
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
# dp[i] 代表爬上第 i 台阶的最低花费
dp = [0] * (n+1)
dp[0] = 0
dp[1] = 0
for i in range(2, n+1):
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
return dp[n]
2、优化动规
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
# dp[i] 代表爬上第 i 台阶的最低花费
# 只需记住前 2 步台阶的花费
dp = [0, 0]
dp[0] = 0
dp[1] = 0
for i in range(2, n+1):
dpi = min(dp[1]+cost[i-1], dp[0]+cost[i-2])
dp[0], dp[1] = dp[1], dpi
return dp[1]