前言
作者：小蜗牛向前冲
** **
本期我们将探讨动态规划，并提供5道经典动态规划问题，难度由浅入深。
一、什么是动态规划
1、什么是动态规划
在学习算法的过程中，我们往往会遇到一些算法题是要用动态规划来解决。
但是做为小白的我们哪里知道动态规划是什么？
从概念上说
动态规划（Dynamic Programming）是一种解决复杂问题的算法设计技术。它通常用于解决具有重叠子问题和最优子结构性质的问题，通过将问题分解为更小的子问题，并利用子问题的解来构建原始问题的解。
看完概念我们知道什么是动态规划，求重叠类子问题的 一般会用到动态规划的思路。
那我们如何求学习动态规划
2、动态规划的学习
对于算法类题目，在我们掌握算法的基本原理后，就是进行大量刷题，进经验的总结。
求解动态规划的五步骤：
1、状态表示
在求解过程中，我们往往要创建dp表(其实就是数组），状态表示就是我们要找出dp表中值的含义是什么。
状态表 怎么来？
- 根据题目要求
- 经验+题目要求
- 分析题目的过程中，发现重复子问题
** 2、状态转移方程**
简单说是和dp[i]有关的一个方程
** 3、初始化**
保证在填写dp表的时候不越界
**4、填写顺序 **
根据前面的计算得来，可以从前往后，也可以从后往前。
** 5、返回值**
根据题目要求+状态表示
讲完了解题步骤，下面就进行刷题训练。
特别提醒：后面博客会带领大家由易到难进行刷题，每期都为五题。
二、动态规划刷题
1、第 N 个泰波那契数
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数
n，请返回第 n 个泰波那契数 Tn 的值。
示例 1：
**输入：**n = 4 **输出：**4 **解释：** T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4示例 2：
**输入：**n = 25 **输出：**1389537提示：
0 <= n <= 37- 答案保证是一个 32 位整数，即
answer <= 2^31 - 1。
a、解题思路：
1、题目中的状态表示是什么？
dp[i] 表⽰：第 i 个泰波那契数的值。
2、状态转移方程
由题目意很很容易知道是T(n) = T(n-1)+T(n-2)+T(n-3)
3、初始化dp表
为了防止数组越界我们只需要初始化:
dp[0]=0;
dp[1]=1;
dp[2]=1;
4、 填表顺序
由状态方程+题意知道从左往右填写到N
5、返回值
根据题目要求和dp[i]就为dp[n]
b、代码
class Solution {
public:
int tribonacci(int n)
{
//动态规划
//1.创建dp表
//2.初始化表
//3.填表
//4.返回值
//处理边界情况
if(n==0)return 0;
if(n==1||n==2)return 1;
//1、创建dp表
vector<int> dp(n+1);
//2、初始化表
dp[0]=0,dp[1]=1,dp[2]=1;
//3、填表
for(int i = 3;i<=n;i++)
{
dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
}
//4、返回
return dp[n];
}
};
**Leetcode 测试结果： **
2、 面试题 08.01. 三步问题
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1:
** 输入**：n = 3 ** 输出**：4 ** 说明**: 有四种走法示例2:
** 输入**：n = 5 ** 输出**：13提示:
- n范围在[1, 1000000]之间
** a、解题思路：**
从0位置开始跳，下面我们来思考一下题意：
----->（表示跳台阶）
n=1时候
从0----->1
走法为1
n=2时候
从0----->2
或者说我们让1----->2因为从 0----->1的走法我们已经考虑过了
走法为2
n=3时候
从0----->3或者说
我们让1----->3因为从 0----->1的走法我们已经考虑过了走法为1
也可以2----->3因为从 0----->2的走法我们已经考虑过了走法为2
走法为1+1+2=4
n=4时候
不管怎么说先走到1，在从1----->4走法为1
不管怎么说先走到2，在从2----->4走法为2
不管怎么说先走到3，在从3----->4走法为4
总共走法：1+2+4=7
大家这里是不是已经思路清晰起来了
1、转态表示
以i位置为结尾，正好是到达第N个台阶，所以我们认为：
dp[i]表示：到达i位置时，一共有多少方法。
** 2、状态转移方程**
以i位置的状态，最近进的一步进行划分
从(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] ;
3、初始化
这里我们注意我们用不到i==0,因为0台阶的研究没有意义。
** dp[1] = 1, dp[2] = 2, dp[3] = 4;**
4、 填表顺序
根据前面的推断肯定是从左往右。
5、返回值
根据题目要求和dp[i]就为dp[n]
b、代码
这题虽然和第一题非常相似但是有细节要处理、
class Solution {
public:
//取模
const int MOD = 1e9 + 7;
int waysToStep(int n)
{
//处理边界情况：
if (n == 1 || n == 2)return n;
if (n == 3)return 4;
//创建dp表
vector<int> dp(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]) % MOD + dp[i - 3]) % MOD;
}
//返回
return dp[n];
}
};
**Leetcode 测试结果： **
3 、746. 使用最小花费爬楼梯
给你一个整数数组
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
a、解题思路
这里我们要注意到达楼顶，应该是const数组最后一个位置的下一个位置
这里我们有二种思路：
思路一：
1、转态表示
以i位置为结尾，正好是楼顶，所以我们认为：
dp[i]表示：到达i位置时，最小花费
** 2、状态转移方程**
根据最近的一个位置划分
先到达i-1的位置，然后支付const[i-1],走一步， 花费：dp[i-1]+cost[i-1]
先到达i-2的位置，然后支付const[i-2],走一步， 花费：dp[i-2]+cost[i-2]
所以dp[i] =min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
3、初始化
保证dp表不越界就好dp[0]=dp[1]=0;
4、 填表顺序
从左往右
5、返回值
dp[n]
思路2：
1、转态表示
以i位置为起点，到达楼顶，所以我们认为：
dp[i]表示：从i位置出发到达楼顶，此时最小花费
** 2、状态转移方程**
根据最近的一个位置划分
- 支付const[i],往后走一步， 从i+1位置出发到楼顶，花费：dp[i+1]+cost[i]
- 支付const[i],往后走二步， 从i+2位置出发到楼顶，花费：dp[i+2]+cost[i]
所以dp[i] =min(dp[i+1]+cost[i],dp[i+2]+cost[i]);
3、初始化
保证dp表不越界就好dp[n-1]=cost[n-1],dp[n-2]=cost[n-2];
4、 填表顺序
从右往左
5、返回值
min(dp[0],dp[1]);
b、代码
这里有二种解题思路：
思路一：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost)
{
//处理边界情况
int n = cost.size();
if(n==0||n==1)return cost[n];
//创建dp表
vector<int> dp(n+1);
//填表
for(int i = 2;i<=n;i++)
{
dp[i] =min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
//返回
return dp[n];
}
};
**Leetcode 测试结果： **
解法二：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost)
{
int n = cost.size();
//创建dp表
vector<int> dp(n+1);
//初始化
dp[n-1]=cost[n-1],dp[n-2]=cost[n-2];
//填表
for(int i = n-3;i>=0;i--)
{
dp[i] = min(dp[i+1]+cost[i],dp[i+2]+cost[i]);
}
//返回
return min(dp[0],dp[1]);
}
};
**Leetcode 测试结果： **
4、解码方法
一条包含字母
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只包含数字，并且可能包含前导零。
a、解题思路
看我们题目后，根据经验此题位动态规划解题
1、转态表示
首先我们想以i位置为结尾表示什么
dp[i]表示：以i位置结尾的时候，解码的方法有多少种
** 2、状态转移方程**
根据最近的一个位置划分
让s[i]单独解码的时候,假设a=s[i]
- 成功,a!='0'（或者说是a>='1'&&a<='9'），解码的种类有dp[i-1]种
- 失败为0
让s[i-1]和s[i]组合进行解码 假设组合为b
- 成功b>='10'&&b<='26',解码的种类有dp[i-2]种
- 失败为0
有同学可能会想为什么不让dp[i]和dp[i+1]进行组合，但是大家 要明白，填表到dp[i]的时候，我们是知道dp[i-1]有多少种解码，但是我们不知道dp[i+1]有多少种解码。
所以状态转移方法为
单独解码
dp[i] +=dp[i-1];
组合解码
dp[i]=dp[i-2];
3、初始化
保证dp表
dp[0] = s[0]!='0';
if(s[0]!='0'&&s[1]!='0') dp[1] +=dp[0];
//这里我们还要把组合转换为数字进行判断
int t = (s[0]-'0')*10+(s[1]-'0');
if(t>=10&&t<=26) dp[1] +=1;
4、 填表顺序
从左往右
5、返回值
dp[n-1]
b、代码
class Solution {
public:
int numDecodings(string s)
{
//创建dp表
int n = s.size();
vector<int> dp(n);
//初始化
dp[0] = s[0]!='0';
//处理边界情况
if(n==1) return dp[0];
//单解码
if(s[0]!='0'&&s[1]!='0') dp[1] +=dp[0];
//组合起来
int t = (s[0]-'0')*10+(s[1]-'0');
if(t>=10&&t<=26) dp[1] +=1;
//填表
for(int i = 2;i<n;i++)
{
//单解码
if(s[i]!='0') dp[i] +=dp[i-1];
//双解码
int t = (s[i-1]-'0')*10+(s[i]-'0');
if(t>=10&&t<=26) dp[i] +=dp[i-2];
}
//返回
return dp[n-1];
}
};
**Leetcode 测试结果： **
**c、代码优化 **
不知道大家分发现没，我们在初始化的代码和填表的代码，有着非常相似的特色，那我们能不能进行优化呢？
其实是可以的，多一个数组的空间就可以了。
简单的理解就是，把初始化的过程和填表合并了。但要注意二个问题：
那个虚拟节点dp[0]填写多少？后面大家做都了这种题，很多情况下都是填写0但，但是这里却是填写**dp[0]=1; **
为什么了，因为我们这里要保证后面填写的正确
比如：在进双解码的时候dp[i]+=dp[i-2]，如何i=2时候，这里我们吧dp[0]初始化为0就会漏掉这种情况。
下标映射关系如上图。
class Solution {
public:
int numDecodings(string s)
{
//创建dp表
int n = s.size();
vector<int> dp(n+1);
//初始化
dp[0] = 1;//保证后面的填表的正确性
//处理边界情况
dp[1] = s[1-1]!='0';
if(n==1) return dp[1];
//填表
for(int i = 2;i<=n;i++)
{
//单解码
if(s[i-1]!='0') dp[i] +=dp[i-1];
//双解码
int t = (s[i-2]-'0')*10+(s[i-1]-'0');
if(t>=10&&t<=26) dp[i] +=dp[i-2];
}
//返回
return dp[n];
}
};
**Leetcode 测试结果： **
5、不同路径（medium）
一个机器人位于一个
m x n
- *网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
**输入：**m = 3, n = 7 **输出：**28示例 2：
**输入：**m = 3, n = 2 **输出：**3 **解释：** 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下示例 3：
**输入：**m = 7, n = 3 **输出：**28示例 4：
**输入：**m = 3, n = 3 **输出：**6提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 109
a、解题思路
看我们题目后，根据经验此题位动态规划解题
1、转态表示
首先我们想以i，j位置为结尾表示什么
dp[i][j表示：以i,j位置结尾的时候，机器人到这里有多少条路径
** 2、状态转移方程**
根据最近的一个位置划分
我要求到[i,j] 路径，本质上就是求dp[i - 1][j] + dp[i][j - 1]的路径和
所以状态转移方法为
dp[i][j] = dp[i-1][j]+dp[i][j-1];
3、初始化
这里我们要初始化，就是在二维数组多开一行和一列，但我们要思路多开的行列填什么呢（一切都是为了填表走服务）？，很明显，在根据dp[i][j] = dp[i-1][j]+dp[i][j-1];填写表格的时候，走一步就到终点，那最外层从从到都应该填1（dp[i][j表示：以i,j位置结尾的时候，机器人到这里有多少条路径），为达到这不目的，应该把dp[0][1]=1其余为0。
4、 填表顺序
从上往下填写每一行，每一行都是从左往又开始填写
5、返回值
dp[m][n]
b、代码
class Solution {
public:
int uniquePaths(int m, int n)
{
//创建二维dp表
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//初始化
dp[0][1] = 1;
//填表
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
};
**Leetcode 测试结果： ** 
版权归原作者 小蜗牛~向前冲 所有， 如有侵权，请联系我们删除。