算法训练营第二十八天 | 动态规划（一）

一、动态规划理论基础

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

动态规划五部曲

确定 dp 数组以及下标的含义

这一步是基础，需要定义一个合适的数据结构（通常是数组或二维数组等）来存储子问题的解，即 dp 数组。dp 数组的每个元素代表一个子问题的解，而其下标的含义则决定了如何描述和区分不同的子问题。例如，在一些问题中，dp[i] 可能表示处理到第 i 个元素时的最优解；在二维情况下，dp[i][j] 可能表示在某种条件下，涉及前 i 个元素且满足另一个维度条件为 j 时的最优解。合理定义 dp 数组及其下标的含义，能清晰地表示问题的状态和子问题之间的关系。

确定递推公式

递推公式是动态规划的核心，它描述了如何从已知的子问题的解推导出当前子问题的解。具体来说，就是根据 dp 数组下标的含义，分析当前状态（子问题）与之前状态（子问题）之间的联系。通常会考虑问题的不同情况或决策，通过对这些情况的分析和组合，得到一个数学表达式来计算 dp 数组中当前位置的值。比如，dp[i] 可能依赖于 dp[i-1] 、dp[i-2] 等前面位置的值，通过某种运算（如加法、乘法、取最大值等）得到 dp[i] 的值。递推公式的正确性直接决定了动态规划算法能否得到正确的结果。

dp 数组初始化

初始化 dp 数组是为了给动态规划的递推过程提供一个起始点。需要根据问题的实际情况和 dp 数组下标的含义，确定一些最基本的子问题的解。这些基本子问题通常是最简单的情况，比如当 i=0 或 j=0 时的情况。例如，在某些问题中，dp[0] 可能表示初始状态下的解，直接根据问题条件赋值为一个确定的值；在二维 dp 数组中，dp[0][0] 、dp[0][j]（固定 i=0 ）或 dp[i][0] （固定 j=0 ）等可能需要根据具体情况进行初始化。正确的初始化能确保递推过程从合理的起点开始，避免后续计算出现错误。

确定遍历顺序

遍历顺序决定了如何按照一定的逻辑依次计算 dp 数组中的每个元素。这一步需要考虑 dp 数组中元素之间的依赖关系，即当前元素的计算是否依赖于其他元素已经计算好的值。通常有正向遍历（从小到大）、反向遍历（从大到小）等方式。例如，如果dp[i] 的计算依赖于 dp[i-1] ，那么就需要从 i=1 开始依次递增计算 dp[i] ；在二维数组中，可能需要先遍历一个维度，再遍历另一个维度，或者根据问题的特点采用特殊的遍历顺序。合理的遍历顺序能保证在计算每个 dp 元素时，其所需的依赖值都已经计算完成。

举例推导 dp 数组

这一步是对前面四个步骤的验证和加深理解。通过选取一个简单的具体例子，手动按照前面确定的 dp 数组定义、递推公式、初始化方法和遍历顺序来逐步计算 dp 数组中的值。在推导过程中，可以清晰地看到每个子问题的解是如何得到的，以及整个动态规划的计算过程是否符合预期。如果在推导过程中发现问题，比如递推公式计算结果不符合逻辑、初始化值导致后续计算错误等，可以及时调整前面的步骤，确保动态规划算法的正确性。

二、Leetcode 509. 斐波那契数

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

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

示例：

原文链接：https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html
题目链接：https://leetcode.cn/problems/fibonacci-number/description/
视频讲解：https://www.bilibili.com/video/BV1f5411K7mo/

动态规划的入门题目，很简单，但是我们还要按照递归五部曲来。

确定 dp 数组以及下标的含义：
很显然，本题的递归数组就是这个斐波那契数列，下标对应着第几个元素。

确定递推公式：
根据斐波那契数列的定义，我们很容易知道本题的状态方程为：dp[i]=dp[i-1]+dp[i-2]

dp 数组初始化:
根据题目描述，斐波那契数列的第一个元素为 0，第二个元素为 1，故数组的初始化为 dp[0]=0，dp[1]=1。

遍历顺序：
我们需要从前两个元素推出下一个元素，所以我们的遍历顺序是从前到后。

由于遍历中出现了下标 i-1 和 i-2，并且我们数组前两个元素已经被初始化，所以我们遍历的范围是 (2, n)。

代码：

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

三、Leetcode 70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例：

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

引用：

原文链接：https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html
题目链接：https://leetcode.cn/problems/climbing-stairs/description/
视频讲解：https://www.bilibili.com/video/BV17h411h7UH/

动态规划五部曲：

确定 dp 数组以及下标的含义：
本题的 dp 数组含义为，爬到第 i 阶楼梯需要多少步。

确定递推公式：
本题目的难点在于确定递推公式。

我们爬到 i-1 阶的时候，需要 dp[i-1] 多步，当我们下一步想迈一阶的时候，那么我们趴到 i 阶就需要 dp[i-1] 步。
我们爬到 1-2 阶的时候，需要 dp[i-2] 步，当我们下一步想要爬两阶的时候，那么我们趴到 i 阶就需要 dp[i-2] 步。
所以我们第 i 阶共有两种选择，那么第 i 阶就一共需要 dp[i-1] + dp[i-2] 步。
故递推公式为 dp[i]=dp[i-1]+dp[i-2] 。

dp 数组初始化:
当 n 等于 0 的时候没有任何意义，所以我们不对 dp[0]初始化，由题目描述很容易得知数组的初始化为 dp[1]=1，dp[2]=2。

遍历顺序：
当前状态需要从前两个状态推出，所以我们的遍历顺序为从前到后。

由于遍历中出现了下标 i-1 和 i-2，并且我们数组前三个元素已经被初始化，所以我们遍历的范围是 (3, n)。

代码：

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

四、Leetcode 746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例：

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

引用：

原文链接：https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html
题目链接：https://leetcode.cn/problems/min-cost-climbing-stairs/description/
视频讲解：https://www.bilibili.com/video/BV16G411c7yZ/

动态规划五部曲：

确定 dp 数组以及下标的含义：
本题的 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] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]) ;

dp 数组初始化:
只初始化 dp[0] 和 dp[1] 就够了，其他的最终都是 dp[0] dp[1]推出。我们默认在第一个台阶是不需要花费的

遍历顺序：
当前状态需要从前两个状态推出，所以我们的遍历顺序为从前到后。

由于遍历中出现了下标 i-1和i-2，并且我们数组前两个元素已经被初始化，所以我们遍历的范围是 (2, len(cost)+1)。

代码：

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)]  # 返回到达楼顶的最小花费