算法训练之动态规划（一）
♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥
♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥
♥♥♥我们一起努力成为更好的自己~♥♥♥
♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥
♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥
✨✨✨✨✨✨ 个人主页✨✨✨✨✨✨
在前面，我们练习了很多不同类型的题目，这一篇博客，我们来看看算法中比较重要的知识点——动态规划~准备好了吗~我们发车啦~🚗🚗🚗🚗🚗🚗
目录
前置知识
第N个泰波那契数
使用最小花费爬楼梯
状态表示方法一
状态表示方法二
解码方法
常规解法
优化解法
前置知识
在正式开始动态规划的题目练习之前，我们来看看动态规划的一般步骤~
一般步骤：
1、创建一个dp表，进行状态表示（状态表示就是dp表里面的值dp[i]有什么含义）
怎么得到状态表示呢？——一般是经验+题目要求
2、状态转移方程
dp[i]等于什么，怎么推导出dp[i]
3、初始化（保证填表的时候不越界）
4、填表顺序
正确的填表顺序是为了填写当前的状态所需要的状态是已经得到了的~
5、返回结果
根据题目要求和状态表示返回最终的结果~
仅仅是说可能有点抽象，接下来我们会结合具体的题目来进行了解这些一般步骤~接下来我们根据这些步骤来看看下面的这些题目~
第N个泰波那契数
第N个泰波那契数
这个题目一看与我们前面写过的斐波那契数有点类似，不过这里是前面三个数的和构成了当前的数~
接下来，我们根据步骤一步步来分析：
1、状态表示
结合这里的题目要求+经验：我们这里的状态表示dp[i]可以是当前位置的泰波那契数
2、状态转移方程
这个题目很容易分析出当前位置dp[i]也就是前面三数之和：
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
3、初始化
我们可以看到，状态转移方程里面有dp[i-1],dp[i-2],dp[i-3],当i=1的时候显然会出现越界的情况，所以我们需要进行初始化
根据题目可以得到：
dp[0]=0,dp[1]=1,dp[2]=1
4、填表顺序
我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前向后
5、返回结果
dp表的第i个位置就是第i个泰波那契数，直接返回dp[n]就是我们的结果
这里还需要添加一步就是处理边界情况
题目给出的n的范围是0~37，当n=0，1，2的时候会出现越界，直接返回就好了~
接下来，我们来进行代码实现：
class Solution
{
public:int tribonacci(int n) {//1、创建dp表vector<int> dp(n+1);//处理边界情况if(n==0) return 0;if(n==1||n==2) return 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];}
};
可以看到分析完成之后，这里的代码还是比较简单的~
算法复杂度：
时间复杂度是O（N），空间复杂度O（N）
那么有没有什么办法让空间复杂度变为O（1）呢？答案是有的，因为我们只需要得到第N个泰波那契数，那么我们只需要三个变量来模拟这个相加的过程就可以了~
优化：
class Solution
{
public:int tribonacci(int n) {//同样需要处理边界情况if(n==0) return 0;if(n==1||n==2) return 1;//创建三个变量模拟相加过程int a=0,b=1,c=1;int d=0;//最终结果int count=n-2;//需要相加次数while(count--){d=a+b+c;//新得到的数//更新前面三个数a=b;b=c;c=d;}//返回结果return d;}
};
这个方法我们也把它叫做滚动数组~可以极大地优化空间复杂度~
使用最小花费爬楼梯
使用最小花费爬楼梯
我们同样可以一步步来分析：
注意点：根据示例我们可以知道楼顶不是最后一个下标的位置，而是最后一个下标后面的那一个位置~
状态表示方法一
1、状态表示
结合这里的题目要求+经验：我们这里的状态表示dp[i]是到该台阶的最小花费是多少（也就是以i位置为结尾的最小花费）
2、状态转移方程
我们以离【i】位置最近的状态分析状态转移方程
1、到达该台阶，可能是从第【i-1】位置花费cost【i-1】走一步到达的
2、到达该台阶，可能是从第【i-2】位置花费cost【i-2】走两步到达的
因为是最小花费，所以应该是两种情况中花费最少的那一个，状态转移方程也就是：
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
3、初始化
我们可以看到，状态转移方程里面有dp[i-1],dp[i-2],当i=0、1的时候显然会出现越界的情况，所以我们需要进行初始化
根据题目（可以从下标为0或者为1的位置开始爬楼梯，所以到可以得到到达下标为0或者为1的位置是不需要花钱的），所以初始化：
dp[0]=0,dp[1]=0
4、填表顺序
我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前向后
5、返回结果
楼顶是最后一个下标后面的那一个位置~直接返回dp[n]就是我们的结果
这里不需要添加处理边界情况了，题目给出长度的范围是2~1000，直接返回就好了~
代码实现：
class Solution
{
public:int minCostClimbingStairs(vector<int>& cost) {//1、创建dp表int n=cost.size();//楼顶是最后一个下标后面的那一个位置vector<int> dp(n+1,0);//里面的值全部初始化为0//2、初始化 dp[0],dp[1]已经在前面初始化为0了//3、根据状态转移方程填表for(int i=2;i<=n;i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}//4、返回结果return dp[n];}
};
这是第一种状态表示方式——以【i】位置为结尾，到达【i】位置的最小花费~接下来我们来看看第二种状态表示方法~
状态表示方法二
1、状态表示
前面的状态表示是以【i】位置为结尾，到达【i】位置的最小花费~我们这里的状态表示dp[i]是以i位置为起点到达楼顶的最小花费
2、状态转移方程
我们以离【i】位置最近的状态分析状态转移方程，同样有两种情况
1、从【i】位置开始花费cost【i】走一步到达第【i+1】位置再加上以第【i+1】位置为起点到达楼顶的最小花费~
2、从【i】位置开始花费cost【i】走两步到达第【i+2】位置再加上以第【i+2】位置为起点到达楼顶的最小花费~
因为是最小花费，所以应该是两种情况中花费最少的那一个，状态转移方程也就是：
dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i])
3、初始化
我们可以看到，状态转移方程里面有dp[i+1],dp[i+2],当i=n-1,n的时候显然会出现越界的情况，所以我们需要进行初始化
根据题目i=n-1的时候往上走一步花费cost[i-1]就可以了，i=n的时候已经在楼顶不需要花钱了，所以初始化：
dp[n-1]=cost[i-1],dp[n]=0
4、填表顺序
我们这里的逻辑是从后面依次推出前面的，所以填表顺序是从后向前
5、返回结果
起点位置可能是1，也可能是0，返回dp[0]和dp[1]的较小值就是我们的结果
代码实现：
class Solution
{
public:int minCostClimbingStairs(vector<int>& cost) {//1、创建dp表int n=cost.size();vector<int> dp(n+1);//2、初始化dp[n-1]=cost[n-1];dp[n]=0;//3、根据状态转移方程填表for(int i=n-2;i>=0;i--){dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i]);}//4、返回结果return min(dp[0],dp[1]);}
};
当然，这里的dp表大小也可以创建为n个大小，只是初始化以及填表的实现需要注意一下范围~
解码方法
解码方法
接下来，我们来分析一道有点难度的题目~
常规解法
首先分析一下题目，题目给出了解码方式，现在我们需要又数字转换为编码，A~Z的字符依次对应的是1~26，这就说明0是没有办法解码的，同时前置0，比如06也是没有办法进行解码的~
所以解码可以分为以下两种情况：
1、单独一个字符解码
2、与附近的字符组合进行解码，只能再结合一位
接下来，我们就按照以前的思路来进行一步步的分析：
1、状态表示
结合这里的题目要求+经验：我们这里的状态表示为dp[i]是以【i】位置为结尾，一共有多少种解码方式
2、状态转移方程
我们以离【i】位置最近的状态分析状态转移方程，我们可以分为单独解码和组合解码两种方式来进行讨论：
1、以【i】位置为结尾，如果【i】位置可以进行单独解码，那么就说明【i】位置的解码方式种数也就需要加上【i-1】位置解码种数~否则不能成功解码（比如为0），这说明前面解码是有问题的，那么就不需要加~
2、以【i】位置为结尾，如果【i】位置与【i-1】位置可以进行组合解码，那么就说明【i】位置的解码方式种数也就需要加上【i-2】位置解码种数~否则不能成功解码（比如为06），这说明前面解码是有问题的，那么就不需要加~
根据分析也就可以得到状态转移方程也就是：
dp[i]=dp[i-1]+dp[i-2]
是否加dp[i-1]或者dp[i-2]需要先进行判断~
3、初始化
我们可以看到，状态转移方程里面有dp[i-1],dp[i-2],当i=0、1的时候显然会出现越界的情况，所以我们需要进行初始化
根据题目当i=0的时候，目前只有一个字符，如果可以单独解码的话，那么dp[0]=1,否则为0，也就是dp[0]有0或者1这两种情况；
当i=1的时候，如果可以1位置可以单独解码的话，那么dp[1]+=dp[0],如果还可以组合解码的话，那么dp[1]+=1，也就是dp[1]有0或者1或者2这三种情况
这里涉及到判断就不给出具体结论，我们在代码中会进行实现~
4、填表顺序
我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前向后
5、返回结果
根据状态表示和题目要求，直接返回dp[n-1]就是我们的结果
这里需要我们处理边界情况，当长度为1的时候，dp[1]是越界的，我们直接返回dp[0]的结果就可以了
代码实现：
class Solution
{
public:int numDecodings(string s){//1、创建dp表int n = s.size();vector<int> dp(n, 0);//最开始就初始化为0//2、判断进行初始化//dp[0]if (s[0] != '0') dp[0] = 1;//不为0就说明可以单独解码// 处理边界情况if (n == 1) return dp[0];//dp[1]if (s[1] != '0') dp[1] += dp[0];//可以单独解码，也就可以加上dp[0]解码数//判断是否可以组合解码int t = (s[0] - '0') * 10 + (s[1] - '0');if (t >= 10 && t <= 26)//判断两位数是否有效dp[1] += 1;//3、根据状态转移方程填表for (int i = 2; i < n; i++){//先判断//1、是否可以单独解码if (s[i] != '0') dp[i] += dp[i - 1];//2、是否可以组合解码int tt = (s[i - 1] - '0') * 10 + (s[i] - '0');if (tt >= 10 && tt <= 26){dp[i] += dp[i - 2];}}//4、返回结果return dp[n - 1];}
};
顺利通过~
优化解法
事实上，这一段代码还可以进行优化，我们可以发现初始化和循环内部的代码事实上是高度类似的，我们可不可以把初始化的代码也写进循环里面呢？答案是可以的，我们只需要多开辟一个空间就可以了~不过这个方法有两个注意点~
1、多开的那一个空间表示什么？
这里我们多开一个空间是想把初始化的代码写入循环中，避免越界的情况出现，我们初始化最开始是处理dp[0]和dp[1],那么我们优化一下就让dp1[i]的数据放入dp2[i+1]的位置，这样dp2[2]+=dp2[1]和dp2[2]+=dp2[0]（也就是处理最开始两个字符）就不会出现越界情况，那么我们多开的空间显然就是dp2[0],那么dp2[0]的值应该是多少呢？
使用dp2[0]是在dp2[2]+=dp2[0]的时候，如果最开始两个字符可以组合，说明解码总数就得+1，所以我们的dp2[0]=1
2、下标的映射关系
因为多开了一个空间，所以dp表第【i】个位置事实上是字符串s第【i-1】位置的解码总数~所以应该返回dp2[n]了
代码实现：
class Solution
{
public:int numDecodings(string s){//优化——多开一个空间int n = s.size();vector<int> dp(n + 1, 0);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 tt = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');if (tt >= 10 && tt <= 26) dp[i] += dp[i - 2];}return dp[n];}
};
可以发现这样处理，把我们的处理边界情况和初始化的代码极大地简化了，但是使用时候需要注意前面的两个注意点，避免出错~
♥♥♥本篇博客内容结束，期待与各位优秀程序员交流，有什么问题请私信♥♥♥
♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥
✨✨✨✨✨✨个人主页✨✨✨✨✨✨