代码随想录算法训练营Day28 | Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

代码随想录算法训练营Day28 | Leetcode 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

一、斐波那契数

相关题目：Leetcode509
文档讲解：Leetcode509
视频讲解：Leetcode509

1. Leetcode509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

• F(0) = 0，F(1) = 1
• F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

• 思路：

  • 动态规划五部曲：
    • 确定 dp 数组以及下标的含义：第 i 个数的斐波那契数值是 dp[i]
    • 确定递推公式：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]
    • dp 数组如何初始化：dp[0] = 0;dp[1] = 1
    • 确定遍历顺序：从递归公式可以看出，dp[i] 是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历
    • 举例推导 dp 数组：当 N 为10的时候，dp 数组应该是如下的数列：0 1 1 2 3 5 8 13 21 34 55，如果代码写出来，发现结果不对，就把 dp 数组打印出来看看和我们推导的数列是不是一致的

• 动态规划

##动态规划（版本一）
class Solution:
    def fib(self, n: int) -> int:
       
        # 排除 Corner Case
        if n == 0:
            return 0
        
        # 创建 dp table 
        dp = [0] * (n + 1)

        # 初始化 dp 数组
        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 <= 1:
            return n
        
        dp = [0, 1]
        
        for i in range(2, n + 1):
            total = dp[0] + dp[1]
            dp[0] = dp[1]
            dp[1] = total
        
        return dp[1]

##动态规划（版本三）
class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        
        prev1, prev2 = 0, 1
        
        for _ in range(2, n + 1):
            curr = prev1 + prev2
            prev1, prev2 = prev2, curr
        
        return prev2

• 递归

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

二、爬楼梯

相关题目：Leetcode70
文档讲解：Leetcode70
视频讲解：Leetcode70

1. Leetcode70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

• 思路：

  • 动规五部曲：

    • 确定 dp 数组以及下标的含义：爬到第 i 层楼梯，有 dp[i] 种方法。

    • 确定递推公式：从 dp[i] 的定义可以看出 dp[i] 可以由两个方向推出来：

      • 上 i-1 层楼梯，有 dp[i - 1] 种方法，再一步跳一个台阶就是 dp[i] 了。
      • 上 i-2 层楼梯，有 dp[i - 2] 种方法，再一步跳两个台阶就是 dp[i] 了。

      所以 dp[i] 就是 dp[i - 1] 与 dp[i - 2] 之和！

    • dp 数组如何初始化：当 i 为0，dp[i] 应该是多少呢，注意到题目中说了 n 是一个正整数，题目根本就没说 n 有为0的情况，所以本题其实就不应该讨论 dp[0] 的初始化！不考虑 dp[0] 如何初始化，只初始化 dp[1] = 1，dp[2] = 2，然后从 i = 3 开始递推，这样才符合 dp[i] 的定义。

    • 确定遍历顺序：从递推公式 dp[i] = dp[i - 1] + dp[i - 2] 中可以看出，遍历顺序一定是从前向后遍历的。

    • 举例推导dp数组：当 n 为5的时候，dp 数组应该是这样的：
      

  • 拓展：若每次可以爬 1,2,…,m 个台阶，有多少种方法爬到 n 阶楼顶。思路类似本题，题目见 卡码网57.爬楼梯。

• 动态规划

##动态规划（版本一）
# 空间复杂度为O(n)版本
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, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[n]

##动态规划（版本二）
# 空间复杂度为O(3)版本
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return n
        
        dp = [0] * 3
        dp[1] = 1
        dp[2] = 2
        
        for i in range(3, n + 1):
            total = dp[1] + dp[2]
            dp[1] = dp[2]
            dp[2] = total
        
        return dp[2]

##动态规划（版本三）
# 空间复杂度为O(1)版本
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return n
        
        prev1 = 1
        prev2 = 2
        
        for i in range(3, n + 1):
            total = prev1 + prev2
            prev1 = prev2
            prev2 = total
        
        return prev2

三、使用最小花费爬楼梯

相关题目：Leetcode746
文档讲解：Leetcode746
视频讲解：Leetcode746

1. Leetcode746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
提示：

• cost 的长度范围是 [2, 1000]。
• cost[i] 将会是一个整型数据，范围为 [0, 999] 。

• 思路：

  • 动规五部曲：

    • 确定 dp 数组以及下标的含义：dp[i] 的定义为到达第 i 台阶所花费的最少体力为 dp[i]。

    • 确定递推公式：可以有两个途径得到 dp[i]，一个是 dp[i-1] 一个是 dp[i-2]：

      • dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
      • dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

      为了所费体力最小，选择从 dp[i - 1] 和 dp[i - 2] 跳至 dp[i] 耗费少的，即 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。

    • dp 数组如何初始化：由递归公式，只初始化 dp[0] 和 dp[1] 就够了，其他的最终都是 dp[0] 与 dp[1] 推出。题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说到达第0个台阶是不花费的，但从第0个台阶 往上跳的话，需要花费 cost[0]。所以初始化 dp[0] = 0，dp[1] = 0。

    • 确定遍历顺序：因为是模拟台阶，而且 dp[i] 由 dp[i-1] 与 dp[i-2] 推出，所以是从前到后遍历 cost 数组就可以了。

    • 举例推导 dp 数组：例：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，模拟一下 dp 数组的状态变化，如下：
      

• 动态规划

##动态规划（版本一）
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(cost) + 1):
            # 在第i步，可以选择从前一步（i-1）花费体力到达当前步，或者从前两步（i-2）花费体力到达当前步
            # 选择其中花费体力较小的路径，加上当前步的花费，更新dp数组
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        
        return dp[len(cost)]  # 返回到达楼顶的最小花费

##动态规划（版本二）
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp0 = 0  # 初始值，表示从起点开始不需要花费体力
        dp1 = 0  # 初始值，表示经过第一步不需要花费体力
        
        for i in range(2, len(cost) + 1):
            # 在第i步，可以选择从前一步（i-1）花费体力到达当前步，或者从前两步（i-2）花费体力到达当前步
            # 选择其中花费体力较小的路径，加上当前步的花费，得到当前步的最小花费
            dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2])
            
            dp0 = dp1  # 更新dp0为前一步的值，即上一次循环中的dp1
            dp1 = dpi  # 更新dp1为当前步的最小花费
        
        return dp1  # 返回到达楼顶的最小花费

##动态规划（版本三）
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * len(cost)
        dp[0] = cost[0]  # 第一步有花费
        dp[1] = cost[1]
        for i in range(2, len(cost)):
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
        # 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
        return min(dp[-1], dp[-2])

##动态规划（版本四）
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        prev_1 = cost[0]  # 前一步的最小花费
        prev_2 = cost[1]  # 前两步的最小花费
        for i in range(2, n):
            current = min(prev_1, prev_2) + cost[i]  # 当前位置的最小花费
            prev_1, prev_2 = prev_2, current  # 更新前一步和前两步的最小花费
        return min(prev_1, prev_2)  # 最后一步可以理解为不用花费，取倒数第一步和第二步的最少值