Day 38 DP：509. 斐波那契数, 70. 爬楼梯, 746. 使用最小花费爬楼梯

DP 主要步骤：

• dp 含义，1D， 2D
• 目标
• 递推公式, 状态转移方程
• 初始化
• 遍历顺序

• 举例

  
  

509. 斐波那契数

• 思路
  • example
  • DP, 迭代, 自下而上， dp table
• 复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n 
        dp = [0 for _ in range(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[n]

• 空间优化

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1: 
            return 1
        first, second = 0, 1
        for i in range(2, n+1):
            third = second + first 
            first = second   
            second = third 
        return third

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n  
        first, second = 0, 1
        for i in range(2, n+1):
            third = first + second  
            first = second 
            second = third 
        return third

• DP, 递归，自上而下 (暴力解）

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        return self.fib(n-1) + self.fib(n-2)

• DP, 递归，自上而下, 备忘录（记亿化）

  
  

class Solution:
    def fib(self, n: int) -> int:
        def helper(n):        
            if dp[n] != -1:
                return dp[n]
            if n == 0:
                return 0
            if n == 1:
                return 1
            dp[n] = helper(n-1) + helper(n-2)
            return dp[n]
        dp = [-1] * (n+1)
        return helper(n)

70. 爬楼梯

• 思路
  • example
  • DP
• 复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return n 
        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]

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]

• 空间优化

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1
        first, second = 1, 1
        for i in range(2, n+1):
            third = first + second
            first = second 
            second = third
        return third

746. 使用最小花费爬楼梯

• 思路
  • example
  • 最低花费
  • 顶层：下标n

初始化
dp[0] = 0 不需要花费
dp[1] = 0 不需要花费
for i > 1:

dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
目标：dp[n]

• 复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0 for _ in range(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]

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost) 
        dp = [0 for _ in range(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]  

• 可空间优化成