509. 斐波那契数

题目

思路与解法

class Solution:def fib(self, n: int) -> int:fib = [1] * nif n == 0:return 0if n == 1 or n == 2 :return 1for i in range(2, n):fib[i] = fib[i-1] + fib[i-2]return fib[n-1]

70. 爬楼梯

题目

思路与解法

class Solution:def climbStairs(self, n: int) -> int:# dp数组的含义：第i个台阶有dp[i]种方法达到dp = [1]*(n+1)for i in range(2, n+1):dp[i] = dp[i-1] + dp[i-2] # 第i个台阶能到达的方式的数量 = 前一个台阶和前两个台阶到达方式的总和return dp[n]

746. 使用最小花费爬楼梯

题目

思路与解法

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:# dp数组的含义：第i个台阶花费的最少开销，这里第0层和第1层不花费，是直接从0或1开始的dp = [0]*(len(cost)+1)# 每一层台阶只能从前一个或前两个台阶走上来for i in range(2, len(dp)):dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])return dp[len(cost)]