什么是动态规划？
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。动态规划是一种解决多阶段决策过程最优化问题的数学方法。它通常用于解决具有重叠子问题和最优子结构性质的问题，通过将问题分解为更小的子问题并记录每个子问题的解，最终通过组合这些子问题的解来求得原问题的最优解。动态规划算法通常用于优化问题，如最短路径、最长公共子序列、背包问题等，其核心思想是通过空间换时间，避免重复计算，从而提高效率。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
动态规划问题五部曲：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
1斐波那契数
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例 1：
输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
0 <= n <= 30
思路：
定义dp数组：
dp[i]表示斐波那契数列第i个数的值。设置初始条件：确定了斐波那契数列的起始值
dp[0] = 0和dp[1] = 1。递推公式：使用经典的递推关系式
dp[i] = dp[i - 1] + dp[i - 2]计算出每个dp[i]的值。遍历顺序：从
dp[2]到dp[N]，依次计算每个值，确保每个子问题的解只计算一次。举例推导dp数组：通过具体的例子（如计算
dp[5]）来展示每一步计算的过程，加深理解。
// 以N=5为例，计算过程如下：
// dp[0] = 0
// dp[1] = 1
// dp[2] = dp[1] + dp[0] = 1 + 0 = 1
// dp[3] = dp[2] + dp[1] = 1 + 1 = 2
// dp[4] = dp[3] + dp[2] = 2 + 1 = 3
// dp[5] = dp[4] + dp[3] = 3 + 2 = 5代码：
class Solution {
public:
int fib(int N) {
// 如果N小于等于1，直接返回N，因为斐波那契数列中F(0)=0，F(1)=1
if (N <= 1) return N;
// 创建一个大小为N+1的dp数组，用来存储斐波那契数列的值
vector<int> dp(N + 1);
// 设置初始条件：斐波那契数列的前两个数
dp[0] = 0; // F(0) = 0
dp[1] = 1; // F(1) = 1
// 使用动态规划递推公式计算从dp[2]到dp[N]的值
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
// 返回斐波那契数列第N个数的值
return dp[N];
}
};2 爬楼梯
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例 1：
输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
0 <= n <= 30
思路：
1. 确定dp数组（dp table）以及下标的含义
在解决爬楼梯问题时，我们定义一个dp数组：
dp[i]表示爬到第i阶楼梯的方法总数。
2. 确定递推公式
通过分析可得出递推公式：
- 当
i = 1时，dp[1] = 1：爬到第1阶楼梯只有一种方法。 - 当
i = 2时，dp[2] = 2：爬到第2阶楼梯有两种方法（一步一步或者一次两步）。 - 对于
i >= 3，爬到第i阶楼梯的方法数可以通过以下递推关系得到：
[
dp[i] = dp[i - 1] + dp[i - 2]
]
解释：要到达第i阶楼梯，可以从第i-1阶走一步，或者从第i-2阶走两步，因此dp[i]的值等于这两种方式的方法数之和。
3. dp数组如何初始化
根据递推公式，我们需要初始化前两个元素：
dp[1] = 1：爬到第1阶楼梯的方法数为1。dp[2] = 2：爬到第2阶楼梯的方法数为2。
4. 确定遍历顺序
我们从小到大遍历楼梯的阶数，从 i = 3 开始直到 i = n，计算并填充 dp[i] 的值。
5. 举例推导dp数组
以一个具体的例子（如n=5）来推导dp数组的值：
- 初始化：
dp[1] = 1，dp[2] = 2。 - 计算
dp[3]：dp[3] = dp[2] + dp[1] = 2 + 1 = 3。 - 计算
dp[4]：dp[4] = dp[3] + dp[2] = 3 + 2 = 5。 - 计算
dp[5]：dp[5] = dp[4] + dp[3] = 5 + 3 = 8。
因此，爬到第5阶楼梯的方法数为8。
代码：
class Solution {
public:
int climbStairs(int n) {
if (n <= 1) return n; // 如果台阶数小于等于1，则直接返回n，因为下面直接对dp[2]操作了，防止空指针
vector<int> dp(n + 1); // 创建一个大小为n+1的动态规划数组
dp[1] = 1; // 初始化动态规划数组的第一个值为1
dp[2] = 2; // 初始化动态规划数组的第二个值为2
for (int i = 3; i <= n; i++) { // 从第三个值开始计算
dp[i] = dp[i - 1] + dp[i - 2]; // 根据题目要求的规则，计算每个台阶的方法数
}
return dp[n]; // 返回达到第n个台阶的方法数
}
};3使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。
示例 2：
输入：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 。
提示：
2 <= cost.length <= 10000 <= cost[i] <= 999
思路：
1. 确定dp数组（dp table）以及下标的含义
在本问题中，我们定义一个dp数组：
dp[i]表示到达第i个台阶的最小花费。
2. 确定递推公式
根据题意，可以得出递推公式：
到达第
i个台阶的最小花费dp[i]可以由以下两种方式得到：- 从第
i-1个台阶花费cost[i-1]走一步到达； - 或者从第
i-2个台阶花费cost[i-2]走两步到达。
因此，递推公式为：
[
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
]- 从第
3. dp数组如何初始化
根据递推公式，需要初始化前两个元素：
dp[0] = 0：表示起始时在地面上，不花费任何体力。dp[1] = 0：表示从地面上直接跳到第一个台阶，同样不花费体力。
4. 确定遍历顺序
从第三个台阶开始遍历，直到最后一个台阶 cost.size()，计算并填充 dp[i] 的值。
5. 举例推导dp数组
以一个具体的例子来推导dp数组的值（假设 cost = [10, 15, 20]）：
- 初始化：
dp[0] = 0，dp[1] = 0。 - 计算
dp[2]：dp[2] = min(dp[1] + 15, dp[0] + 10) = min(0 + 10, 0 + 15) = 10。 - 计算
dp[3]：dp[3] = min(dp[2] + 20, dp[1] + 15) = min(10 + 15, 0 + 15) = 15。
代码：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size() + 1); // 创建一个大小为 cost.size()+1 的动态规划数组
dp[0] = 0; // 默认第一步都是不花费体力的
dp[1] = 0; // 默认第二步也是不花费体力的
for (int i = 2; i <= cost.size(); i++) { // 从第三步开始计算
// 到达第 i 个台阶的最小花费等于到达第 i-1 个台阶和第 i-2 个台阶的最小花费加上当前台阶的花费的较小值
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.size()]; // 返回到达顶部台阶的最小花费
}
};
