目录
前言
本文主要从三个Leetcode算法题入手，图文并茂的讲解如何使用动态规划解决算法题目。如何定义动态规划表，如何对具体问题分析出状态转移方程，这两个问题是动态规划的核心，本问都会详细说明。
1. 第N个泰波那契数列
（1）题目及示例
题目链接：1137. 第 N 个泰波那契数 - 力扣（LeetCode）
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数
n，请返回第 n 个泰波那契数 Tn 的值。
示例 1：
输入：4
输出：4
解释：n = 4
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
输入：n = 25
输出： 1389537
（2）动态规划解题思路
动态规划是将复杂问题分解为重复的子问题，并通过记录之前的计算结果，推出之后的状态。
泰波那契数列特点很明显，从第四个数开始，是前三个数之和。而这就是这道题的状态转移方程，我们可以使用动态规划的方法解决这道题目。
- 以这题为例，首先我们需要创建一个dp表，即创建一个整形数组，记得数组元素个数是n+1个。
- 其次，初始化前三个数列元素的值。但是这里需要判断n的大小，是否等于0,1或者2。如果是其中之一，就直接返回0或者1。因为不判断直接初始化，会导致数组越界。
- 接着，根据状态转移方程填表。其中该dp表表示泰波那契数列的元素，而该数列元素是前三个元素之和，这个关系就是状态转移方程。
- 最后，泰波那契数列元素从0号开始，说明有n+1个数，所以返回dp表n下标位置的元素即可。
int tribonacci(int n)
{
//1. 创建 dp 表
vector<int> dp(n + 1);
// 判断n大小，防止dp数组越界
if(n == 0)
return 0;
if(n == 1 || n == 2)
return 1;
//2. 初始化
dp[1] = dp[2] = 1;
//3. 填表
for(int i = 3; i < n + 1; i++)
{
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
//4. 返回值
return dp[n];
}分析一下时间复杂度和空间复杂度。上述代码中，需要遍历一次dp表，基本就是n次遍历，时间复杂度是O(n)。在空间上，创建了元素大小为n+1的数组，所以空间复杂度也是O(n)。
（3）优化空间
上面创建dp表，空间复杂度为O(n)。不过这个状态转移方程只跟前三项有关系，我们可以使用滚动数组来优化空间。
因为有三个变量需要初始化，所以我们要使用四个整型变量a、b、c和d。其中前三个变量一开始存储泰波那契数列的三个初始值，d变量用于存储前三个变量的和。
如下图，a、b和c分别初始化为0、1和1。d变量用来存储前三个变量的和。
接着，a赋值为b，b赋值为c，c赋值为d。d继续存储前三个变量之和。
int tribonacci(int n)
{
//1. 创建 dp 表
//2. 初始化
//3. 填表
//4. 返回值
if (n == 0)
return 0;
if (n == 1 || n == 2)
return 1;
int a = 0, b = 1, c = 1, d = 0;
for (int i = 3; i < n + 1; i++)
{
d = a + b + c;
a = b;
b = c;
c = d;
}
return d;
}2.使用最小花费爬楼梯
（1）题目及示例
题目链接：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）解法一
该题需要根据题目给出的具体数组，来求出到达顶部的最小花费。
如果使用动态规划，一般需要创建dp表数组，还要明确dp[i]表示什么状态。在上一题泰波那契数列中，dp[i]表示下标为i数列值，而该数列已经明确i位置的值是前三个数列元素之和。
我们也需要明确dp[i]表示什么，可以从前往后，和从后往前两种思路。先以从前往后思路为例，需要关注当前dp表元素和前面元素的关系。一般来说规定dp[i]为从开始位置到i下标台阶的最小花费。
- 我们支付完当前台阶费用后，可以选择向上爬一个或两个台阶。
- 如果是向上爬一个台阶到达 i 位置台阶，那么之前所在位置是 i-1 的台阶。此时费用到达 i-1 位置的最小花费加上 i-1 位置的费用。其中到达 i-1 位置的最小花费就是dp[i-1]，所以总费用就是dp[i-1]+cost[i-1]。
- 如果是向上爬两个台阶到达 i 位置台阶，那么之前所在位置是 i-2 的台阶。此时费用分析跟上面如出一辙，总费用就是dp[i-2]+cost[i-2]。
- 但是要判断从i-1位置或者i-2位置到达i位置台阶的哪个总费用更少，就取较小值。
写代码时，需要注意初始化dp表前两个值为0，因为可以直接选择从第一个或者第二个台阶开始走。还要走到楼梯顶部是比原数组多一个树，相当于到数组第n+1个数。
int minCostClimbingStairs(vector<int>& cost)
{
int n = cost.size();
// vesion 1 从前往后，dp[i]表示到达i位置时的最小花费
vector<int> dp(n + 1);
for(int i = 2; i <= n; i++)
{
dp[i] = min(cost[i-2]+dp[i-2], cost[i-1]+dp[i-1]);
}
return dp[n];
}（3）解法二
解法一中，dp[i]表示开始位置到 i 位置台阶的最小花费。我们也可以从后往前，定义dp[i]表示从楼顶到 i 位置台阶的最小花费。
- 按照dp表的定义，我们需要从后往前开始完善dp表。首先，只需要n个元素大小的dp表。因为楼顶的位置在n+1的位置。
- 因为我们可以向上爬一个或两个台阶，所以楼顶位置往前一到两个台阶需要初始化为cost数组中的花费。
- 之前的台阶，可以向上爬一个或两个台阶。当向上爬一个台阶时，需要加上当前台阶的费用，即cost[i]，和之前楼顶到达该位置台阶的最小花费，即dp[i-1]。
- 当向上爬两个个台阶时，需要加上当前台阶的费用，即cost[i]，和之前楼顶到达该位置台阶的最小花费，即dp[i-2]。
- 这两种情况下，取最小值，就是楼顶到该台阶的最小花费。
- 最后，返回的时候，需要比较下标为0和1台阶的最小花费，取其中最小值。
int minCostClimbingStairs(vector<int>& cost)
{
int n = cost.size();
// version 2
vector<int> dp(n);
dp[n-1] = cost[n-1], dp[n-2] = cost[n-2];
for(int i = n-3; i >= 0; i--)
{
dp[i] = min(cost[i]+dp[i+1], cost[i]+dp[i+2]);
}
return min(dp[1], dp[0]);
}总的来说，for循环经历大约n次遍历，时间复杂度为O(n)。dp表开辟了大约n个变量的空间，空间复杂度也为O(n)。
3. 解码方法
（1）题目及示例
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'
然而，在解码已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）。
例如，"11106" 可以映射为：
"AAJF" ，将消息分组为 (1, 1, 10, 6)
"KJF" ，将消息分组为 (11, 10, 6)
消息不能分组为 (1, 11, 06) ，因为 "06" 不是一个合法编码（只有 "6" 是合法的）。注意，可能存在无法解码的字符串。
给你一个只含数字的 非空 字符串 s ，请计算并返回解码方法的总数。如果没有合法的方式解码整个字符串，返回 0。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1：
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 2：
输入：s = "06"
输出：0
解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。
（2）解题思路
这个题目也是要根据给出的字符串具体分析解码的个数。
首先，我们需要给dp表下定义，即定义dp[i]表示什么内容或者什么状态。根据题目要求，可知dp[i]可以表示为从下标为0字符到下标为 i 字符最多的解码方式。
其中，我们可以对一到二个字符进行组合，转换成整型变量。假设下面是一个字符数组，每一个格子装有一个字符。下标为i的字符可以独自解码，也可以跟前一个字符组合解码。
因为数字字符本身是ASCII码值，只要减'0’字符ASCII码值48，就可以转换为整型值。
如果s[i]独自解码，用整型变量m表示解码后的数字，那么m = s[i]- '0'。
- 如果满足0<m<9这个条件，可以匹配对应英文字符，解码成功。相当于前面 i-1 个字符加上s[i]这个字符，那么解码数就等于前面i-1 个字符的总解码数，即dp[i-1]。
- 如果m变量等于0，就无法匹配到英文字母，解码失败，那么解码数为0。
如果s[i]与是s[i-1]字符组合在一起解码，把s[i-1]字符转换为整型值用n表示，那么两个字符解码后的整型值，可以表示为 n*10 + m。
- 如果想要解码成功，两个字符转换成的整型值要在26之内，并且不能出现前导0，如"09"这种情况，即满足10<= n*10 + m <=26这个条件。此时相当于 i-2 个字符拼接上这两个字符，不会影响前 i-2 个字符的总解码数，即dp[i-2]。
- 如果不满足上面的条件，解码失败，得到的解码数为0。
可以得到状态转移方程为dp[i] = dp[i-1] +dp[i-2]，不过都是有条件的，需要进行判断。
- dp表元素大小开辟为n个。一开始还需要初始化前两位dp表中的元素。第一个字符判断转换为整型值是否大于0小于9。两个字符组合转换成的整型值判断条件跟上面相同。
- 最后返回dp[n-1]即可。还需要注意判断字符串的字符长度是否大于1！
int numDecodings(string s)
{
int n = s.size();
vector<int> dp(n, 0);
if(s[i] != '0')
dp[0] = 1;
// 需要判断字符个数，否则后面会越界访问
if(n == 1) return dp[0];
if(s[0] != '0' && s[1] != '0')
dp[1] += 1;
int tmp = (s[0] - '0') * 10 + s[1] - '0';
if(tmp >= 10 && tmp <= 26)
dp[1] += 1;
for(int i = 2; i < n; i++)
{
if(s[i] != '0')
dp[i] += dp[i - 1];
int tmp = (s[i - 1] - '0') * 10 + s[i] - '0';
if(tmp >= 10 && tmp <= 26)
dp[i] += dp[i - 2];
}
return dp[n - 1];
}（3）优化
观察上面给出的代码，你会发现for循环中的两个if判断和初始化时的if判断十分相似。那有什么办法可以减少代码的冗余呢？我们可以通过扩建dp表做到。
- 一般来说，将dp表多开一个元素空间，即由原来的n个元素变成n+1个元素。其中扩建后的dp表中的第一个元素，用来为dp表中前几个元素的初始化做准备。
- 因为多了一个元素空间，就可以把字符串s的第一个元素放在dp表第二个位置，直接从字符串s第二个元素开始进行动态规划。
- 此时，需要把dp[0]初始化为1，因为s字符串前两个字符组合转换成的整型值满足条件的话，解码数就为1。
- 还需要注意下标的变化。在for循环中，tmp变量存储的字符s下标都要多减去1。
int numDecodings(string s)
{
// 优化
int n = s.size();
vector<int> dp(n + 1);
dp[0] = 1; // 保证后面的填表是正确的
if(s[0] != '0')
dp[1] = 1;
for(int i = 2; i <= n; i++)
{
if(s[i - 1] != '0')
dp[i] += dp[i - 1];
int tmp = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
if(tmp >= 10 && tmp <= 26)
dp[i] += dp[i - 2];
}
return dp[n];
}总的来说，for循环经历大约n次遍历，时间复杂度为O(n)。dp表开辟了大约n个变量的空间，空间复杂度也为O(n)。
创作充满挑战，但若我的文章能为你带来一丝启发或帮助，那便是我最大的荣幸。如果你喜欢这篇文章，请不吝点赞、评论和分享，你的支持是我继续创作的最大动力！
