今日任务：

1. 动态规划理论基础
2. LeetCode509 斐波那契数
3. LeetCode70 爬楼梯
4. LeetCode746 使用最少花费爬楼梯

资料来源：

1. 代码随想录 | 动态规划理论基础
2. 代码随想录 | LeetCode509 斐波那契数
3. 代码随想录 | LeetCode70 爬楼梯
4. 代码随想录 | LeetCode746 使用最少花费爬楼梯

1 动态规划理论基础

先贴个图在这：

动态规划算法，是用于解决由许多重叠子问题组成的问题的算法。动态规划中，每个状态都是由上一个状态推导而来，这一点区别于贪心算法。比如说背包问题，动态规划每次都需要根据上一个状态来确定下一次拿什么物品，而贪心算法就不用，贪心直接可着最有价值的拿就是了。

动态规划五部曲：

1. 确定dp数组和下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

2 LeetCode509 斐波那契数

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

一道简单的动态规划。按照五部曲走就是：

1. 确定dp数组及下标含义：存储斐波那契数，每个下标对应该下标的斐波那契数
2. 确定递推公式：array[i] = array[i - 1] + array[i - 2]
3. dp数组如何初始化：第1个和第2个元素初始化为0和1
4. 确定遍历顺序：从前向后
5. 举例推导dp数组：0，1，2，3，5，8，13，21，34，55，没有问题。

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

2 LeetCode70 爬楼梯

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

同斐波那契数。另外这道题还有个plus版本，就是如果一次能爬的台阶有1或2或3或4或...或m个，那么有多少种爬楼的方法。这个只需要在递推那块反向遍历一下，取前m个台阶位置的走法的和即可。

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

3 LeetCode746 使用最少花费爬楼梯

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

爬楼梯的plus版本。还是按五部曲走：

1. dp数组和下标的含义：到达第i个台阶时所花费的最少费用
2. 确定递推公式：array[i] = min(cost[i - 1] + array[i - 1], cost[i - 2] + array[i - 2])
3. dp数组初始化：题目给定的是从下标为0的台阶和下标为1的台阶出发都可以，那么array[0]和array[1]花费都为0，初始化为0
4. 遍历顺序：从前往后
5. 举例推导dp数组：示例1，0，0，15，没有问题

python
from typing import List

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp_array = [0] * (len(cost) + 1)
        for i in range(2, len(dp_array)):
            dp_array[i] = min(dp_array[i - 1] + cost[i - 1], dp_array[i - 2] + cost[i - 2])
        return dp_array[-1]