动态规划509|70|746
509斐波那契数
class Solution: def fib(self, n: int) -> int: if n <= 1: return n dp = [0] * (n + 1) dp[0] = 0 dp[1] = 1 for i in range(2, len(dp)): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]
70爬楼梯
class Solution: def climbStairs(self, n: int) -> int: if n == 1: return n dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, len(dp)): dp[i] = dp[i - 2] + dp[i - 1] return dp[n]
746使用最小花费爬楼梯
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: dp = [0] * (len(cost) + 1) dp[0] = 0 dp[1] = 0 for i in range(2, len(dp)): dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]) return dp[-1]