代码随想录 Day-37｜#509 斐波那契数 ｜#70 爬楼梯 ｜#746 使用最小花费爬楼梯

清单

● 509. 斐波那契数
● 70. 爬楼梯
● 746. 使用最小花费爬楼梯

1. LeetCode #509 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n)

2. 思路

初始思路:

1. 确定DP数组及下角标的含义: 第i个数的斐波那契数值就为DP[i]
2. 递推公式: F(n) = F(n-1) + F(n-2)
3. DP数组初始化: DP[0] = 0 / DP[1] = 1
4. 确认遍历顺序：从前往后遍历
5. 举例推导DP数组:(print出来检验正确性)

3. 代码实现

class Solution:
    def fib(self, n: int) -> int:
        #排除特殊情况
        if n < 2:
            return n
        
        #数组
        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[n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode #70 爬楼梯

1. 题目

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

2. 思路

初始思路 :

1. DP[i]: 到第i层共有DP[i]种方法
2. 递推公式:
3. 初始化 DP[0] = 0 DP[1] = 1
4. 遍历顺序:从前往后

3. 代码实现

class Solution:
    def climbStairs(self, n: int) -> int:
        # n > 1 无特殊情况需要处理
        # 创建dp数组
        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]
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode #746 使用最小花费爬楼梯

1. 题目

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

2. 思路

初始思路:

1. dp[i]: 到第i层所需要的最小体力为 dp[i]
2. 递推公式: 选择向上爬一个或者两个台阶，因此选择顶部作为递推公式的右边，需要计算并返回达到楼梯顶部的最低花费:
   dp[i] = min( dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
3. 初始化数组 dp[0] = 0, dp[1] = 1
4. 从前往后遍历cost数组

3. 代码实现

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        #处理特殊情况
        if len(cost) == 2:
            return min(cost)
        
        #dp数组
        dp = [0] * (len(cost)+1)

        #初始化
        dp[0] = 0
        dp[1] = 0

        #循环
        for i in range(2,len(cost)+1):
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

        return dp[len(cost)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18