目录
什么是动态规划？
练习
练习1：斐波那契数
练习2：三步问题
练习3：使用最小花费爬楼梯
练习4：解码方法
什么是动态规划？
动态规划（Dynamic Programming，DP）：是一种常见的算法设计技巧，通常用于解决具有重叠子问题和最优子结构的问题。在动态规划中，将原问题分解成若干子问题，通过求解子问题的最优解来得到原问题的最优解。
如何用动态规划解决问题？
我们可以通过一下5步来解决动态规划问题
1. 确定状态表示
什么是状态表示？
状态表示：指在解决问题时所需要考虑和记录的关键信息。这些状态可以是问题的某种属性或特征，通过对这些状态的定义和记录，可以更好地理解问题的结构，从而设计出高效的动态规划算法。
在解决动态规划问题时，我们通常需要创建动态规划数组（dp），用于存储子问题的解，动态规划数组一般是一个 一维 或 二维 数组，而状态表示，可以理解为 dp表中值的含义 （即dp[i] 或 dp[i][j]的含义）
如何确定状态表示？
1. 从题目要求中确定
2. 根据题目要求 以及 经验 确定
3. 在分析问题的过程中，发现重复子问题，从而确定状态表示
在使用动态规划解决问题时，我们常见的状态表示有两种：
dp[i]：表示以i位置为结尾，...
dp[i]：表示以i位置为起始，...
2. 确定状态转移方程
什么是状态转移方程？
状态转移方程：确定状态之间的转移关系，即如何从一个状态推导出另一个状态。这是动态规划问题的核心，也是最难的一步，也就是需要确定 dp[i] 或 dp[i][j] = ?
如何确定状态转移方程？
需要根据题目要求以及状态表示进行推导
3. 进行初始化
初始化：初始化动态规划数组或表格，通常需要设置起始状态的初始值，为后续的状态转移做准备。（例如：保证后续填表过程中不会发生越界）
4. 确定填表顺序
5. 确定返回值
接下来，我们通过动态规划来解决斐波那契相关练习，帮助我们进一步理解动态规划
练习
练习1：斐波那契数
题目链接：
LCR 126. 斐波那契数 - 力扣（LeetCode）
题目描述：
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
答案需要取模 1e9+7(1000000007) ，如计算初始结果为：1000000008，请返回 1。
示例 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 <= 100
思路分析：
首先，我们来确定状态表示 ，即dp[i] 表示什么
这道题根据题目要求就可直接定义出状态表示：dp[i]：第i个斐波那契数
确定了状态表示后，我们来推导状态转移方程，即dp[i] = ?
题目中其实已经告诉了我们状态转移方程，即 F(n) = F(n - 1) + F(n - 2)
因此，状态转移方程为：
dp[i] = dp[i-1] + dp[i - 2]
接下来，我们对dp数组进行初始化：
从递推公式我们就可以看出：在i = 0 和 i = 1时是没办法进行推导的，因为dp[-2] 和 dp[-1] 不存在
因此，我们在进行填表之前，要先将 0，1位置的值进行初始化，题目中已经告诉我们dp[0] = 0，dp[1] = 1
填表顺序：从左到右依次填写
返回值：要求出第n个斐波那契数，因此，返回值为dp[n]
注意：题目要求答案需要取模 1e9+7(1000000007) ，不要忽略了这个条件
代码实现：
class Solution {
public int fib(int n) {
//处理特殊情况
if(n == 0) return 0;
//创建dp表
int[] dp = new int[n+1];
//初始化
dp[0] = 0;
dp[1] = 1;
//填表
for(int i = 2; i <= n; i++){
dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
}
//返回结果
return dp[n];
}
}优化：
在这道题中，我们可以使用滚动数组进行优化：
由于我们每次确定dp[i]时，只会涉及到三个变量：dp[i-2] dp[i-1] dp[i]，因此，每次求dp[i] 时只需要知道dp[i-1] 和 dp[i-2]的值就可以了，我们可以使用变量 a b c来分别表示 dp[i-2] dp[i-1] dp[i]， c = a + b，这样我们仅需使用三个变量就可以遍历数组
在每次求出c的值后，更新a和b的值（注意先更新a的值（a = b），再更新b的值（b = c）） 使其向后移动，从而确定下一个结果
优化代码：
class Solution {
public int fib(int n) {
//处理特殊情况
if(n == 0) return 0;
//优化
int a = 0, b = 1, c = 1;
for(int i = 2; i <= n; i++){
c = (a + b) % 1000000007;
//更新a和b
a = b;
b = c;
}
//返回结果
return c;
}
}练习2：三步问题
题目链接：
面试题 08.01. 三步问题 - 力扣（LeetCode）
题目描述：
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1:
输入：n = 3 输出：4 说明: 有四种走法
示例2:
输入：n = 5 输出：13
提示:
- n范围在[1, 1000000]之间
思路分析：
小孩每次可以上1阶、2阶或3阶台阶，我们首先来模拟小孩上台阶的过程：
状态表示：
我们以 i 位置为结尾进行分析：
那么在这道题中，以i位置为结尾，则可表示为小孩到达第i阶台阶，
而dp[i]则可表示：小孩到达第i阶台阶时，一共有dp[i]种上楼方式
状态转移方程：
由于小孩一次可以上1阶、2阶或3阶台阶，因此，小孩可以从 第 i-3 或 i-2 或 i-1位置到达第i阶台阶
由于dp[i]： 小孩到达第i阶台阶时，一共有dp[i]种上楼方式，因此，
dp[i-1]： 小孩到达第 i - 1阶台阶时，一共有dp[i - 1]种上楼方式，则从i-1位置到达i位置有dp[i-1]种上楼方式
同理，从i-2位置到达i位置有dp[i-2]种上楼方式，从i-3位置到达i位置有dp[i-3]种上楼方式
因此，dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
初始化：
由于dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，因此，在i = 0, i = 1 以及 i = 2时是没办法进行推导的，
因此我们需要在填表之前，对0，1，2位置的值进行初始化，
由于至少上一阶台阶，因此，我们选择从1位置开始初始化，根据分析：dp[1] = 1, dp[2] = 2, dp[3] = 4
填表顺序：
i位置的值是由 i-1、i-2和 i-3位置的值得到的，因此填表顺序为从左向右
返回值：
要求上到第n阶台阶的方式，因此我们返回dp[n]
注意：由于本题计算的结果可能很多，需要对结果进行取模，在计算时，将三个值先加起来再进行取模（(dp[i-1] + dp[i-2]+ dp[i-3]) % 1000000007）是不可取的（会报错），因此我们每计算一次（每两个数相加），就进行一次取模
代码实现：
class Solution {
public int waysToStep(int n) {
//处理特殊情况
if(n == 1 || n == 2) return n;
//创建dp表
int[] dp = new int[n+1];
//初始化
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
//填表
for(int i = 4; i <= n; i++){
dp[i] = ((dp[i-1] + dp[i-2]) % 1000000007 + dp[i-3]) % 1000000007;
}
//返回
return dp[n];
}
}与练习1相同，由于dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，因此，本题也可以使用滚动数组进行优化：
class Solution {
public int waysToStep(int n) {
//处理特殊情况
if(n == 1 || n == 2) return n;
if(n == 3) return 4;
//创建dp表
//初始化
int a = 1, b = 2, c = 4, d = 0;
//填表
for(int i = 4; i <= n; i++){
d = ((a + b) % 1000000007 + c) % 1000000007;
a = b;
b = c;
c = d;
}
//返回
return d;
}
}练习3：使用最小花费爬楼梯
题目链接：
746. 使用最小花费爬楼梯 - 力扣（LeetCode）
题目描述：
给你一个整数数组 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
思路分析：
可以从0或者1位置开始爬楼梯，当爬到i位置时，需要支付cost[i]继续向上爬楼梯，可以爬到 i + 1 或 i + 2位置，最终求爬到顶楼的最小花费（注意：顶楼在 cost.length 位置，而不是 cost.length - 1位置）
状态表示：
我们以 i 位置为结尾进行分析：
那么在这道题中，以i位置为结尾，则可表示到达第i阶台阶，
而dp[i]则可表示：到达第i阶台阶时的最小花费
状态转移方程：
由于一次只能向上爬一个或两个台阶，因此，只能从i - 2位置 或 i - 1位置到达i位置
由于dp[i]： 到达第i阶台阶时的最小花费，因此，
dp[i-1]： 到达第 i - 1阶台阶时，最小花费为dp[i-1]，则从i-1位置到达i位置的最小花费为 dp[i-1] + cost[i-1]
同理，从i-2位置到达i位置时最小花费为dp[i-2]，则从 i-2 位置到达i位置的最小花费为 dp[i-2] + cost[i-2]
要求到达第i阶台阶时的最小花费，则dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
初始化：
可以从0位置或1位置开始向上爬，因此dp[0] = dp[1] = 0
填表顺序：由于dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])，填表顺序为从左向右
返回值：要求到达顶楼（cost.length）的最小花费，因此返回dp[cost.length]
代码实现：
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
//创建dp表
int[] dp = new int[n + 1];
//填表
for(int i = 2; i <= n; i++){
dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
}
//返回
return dp[n];
}
}练习4：解码方法
题目链接：
91. 解码方法 - 力扣（LeetCode）
题目描述：
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> "1" 'B' -> "2" ... 'Z' -> "26"
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
"AAJF"，将消息分组为(1 1 10 6)"KJF"，将消息分组为(11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
输入：s = "12" 输出：2 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：
输入：s = "226" 输出：3 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3：
输入：s = "06" 输出：0 解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。
提示：
1 <= s.length <= 100s只包含数字，并且可能包含前导零。
思路分析：
对给定的数字字符串进行解码，1-26分别对应A-Z，且在解码时不能出现前导0（如05）
状态表示：
我们以 i 位置为结尾进行分析：
那么在这道题中，以i位置为结尾，则dp[i]则可表示：0 到 i 位置一共有dp[i]种解码方法
状态转移方程：
由于1 - 26 分别对应 A - Z，则一个字母只可能由一个字符或两个字符进行解码得到，因此，以i位置为结尾进行解码时，最后一个字母只可能由当前字母（s[i]）或当前字母和前一个字母（s[i] 和 是[i-1]）进行解码得到
由于dp[i]： 0 到 i 位置一共有dp[i]种解码方法，因此，
dp[i-1]： 0 到 i 位置一共有dp[i]种解码方法，若s[i]能够解码，则以i位置为结尾的字符串共有 dp[i-1]种解码方法，若s[i]不能解码，则解码方法为0
同理，dp[i-2]表示以 i - 2为结尾的字符串一共有dp[i-2]种解码方法，若s[i]和s[i-1]位置组成的数字能够解码，则以i位置为结尾的字符串共有 dp[i-2]种解码方法，否之，则解码方法为0
因此，
若s[i]解码成功（s[i] >= '1' && s[i] <= '9'），则dp[i] += dp[i-1]，否之，dp[i] += 0
若s[i]和s[i-1]位置组成的数字解码成功，则 dp[i] += dp[i-2]，否之，dp[i] += 0
在判断s[i]和s[i-1]位置组成的数字是否解码成功时，我们可以先将其转换为数字 n = (s[i-1] - '0') * 10 + (s[i] - '0')，由于不能出现前导0，因此，若结果在 10 - 26区间内，则解码成功，反之，则失败
初始化：
由于在确定i位置的值时需要 i - 1 和 i - 2位置上的值，因此，我们要先初始化i = 0和 i = 1位置上的值：
dp[0]：若 s[0] >= '1' && s[0] <= '9'，则dp[0] = 1，反之，dp[0] = 1
dp[1]：s[1] >= '1' && s[1] <= '9'，dp[1] += dp[0]，反之，dp[1] += 0
s[0] 和 s[1]结合后数字在[10, 26]区间内，则dp[1] += 1，反之，dp[1] += 0
我们可以发现：前两个位置的初始化方式与填写后续i位置时十分相似，都需要判断字符是否能够
正确解码，因此，我们可以在最前面添加一个辅助节点，来帮助我们进行初始化：
在本题中，添加辅助节点后，就只需要初始化dp[1]，若 s[1] >= '1' && s[1] <= '9'，则dp[1] += dp[0]
在添加辅助节点时需要注意：
1. 辅助节点里的值要保证后续填表过程中不出错
2. 下标的映射关系
添加辅助节点后dp表与s的映射关系变为了 dp[i] - s[i-1]，因此，我们在编写代码时要注意
当s[0]解码正确时，dp[1] += dp[0]，因此，dp[0]应初始化为 1
填表顺序：从左往右
返回值：dp[n]
代码实现：
class Solution {
public int numDecodings(String ss) {
char[] s = ss.toCharArray();
int n = s.length;
//创建dp表
int[] dp = new int[n+1];
//初始化
dp[0] = 1;//保证后续填表正确
if(s[0] > '0' && s[0] <= '9') dp[1] += dp[0];
//填表
for(int i = 2; i <= n; i++){
int num = s[i-1] - '0';//注意下标的映射关系
if(num > 0 && num <= 9) dp[i] += dp[i-1];
num = (s[i-2] - '0') * 10 + s[i-1] - '0';
if(num >= 10 && num <= 26) dp[i] += dp[i-2];
}
//返回
return dp[n];
}
}
