【动态规划专栏】专题一总结

本文主要是介绍【动态规划专栏】专题一总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：动态规划专栏
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

专题一

第 N 个泰波那契数
三步问题
最小花费爬楼梯
解码方法：
- 3.初始化
- 4.填表顺序
- 5.返回值
斐波那契数
思维导图：

在专题一中，我们重点学习了动态规划的第一种类型：斐波那契模型，在程序中我们用四道题进行了练习与巩固。

第 N 个泰波那契数

来源：第 N 个泰波那契数

在第一题中：发现他跟我们的斐波那契数列其实是很相似的，在解决本题中，我们首先对问题进行了变形：
在这里插入图片描述
我们通过变形，得到了一个递推关系式，第四个数是我们对应前三个数的和。为解决此问题呢，我们通过举例子：引出了dp表的概念

dp表其实就是一个一维或者二维数组，而我们要做就是将dp表里面的值填满，而其中dp表里面的值就是我们要的答案。
动态规划基本上分为五步:

1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值

其中状态转移方程由状态表示推出，而3.4.5步则为处理细节问题。

在第一题中，我们的状态表示为：

dp[i]:表示第i个泰波那契数

根据递推式，我们的状态转移方程为;

dp[i]=dp[i-3]+dp[i-2]+dp[i-1]

这道题其实基本上到这就已经结束了，最后不要忘了初始化以及边界处理即可。

代码实现：

class Solution 
{
public:int tribonacci(int n) {//创建dp表vector<int> dp(n+1);//处理边界if(n==0)return 0;if(n==1||n==2)return 1;//初始化dp[0]=0;dp[1]=dp[2]=1;//填表for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2]+dp[i-3];}return dp[n];}
};

三步问题

来源：三步问题

这道题很有意思，我们分析题目：举几个例子：
在这里插入图片描述
规律还是很好发现的，所以状态表示直接就是：

dp[i]:表示到达i位置时，有多少种方法

在分析状态转移方程时，我们要以i位置的状态，来划分问题：
在这里插入图片描述
到达iu位置的时候，我们要观察，他可以如何到达i位置，可以从i-1位置，也可以从i-2位置过来，还可以从i-3位置过来。

因此状态转移方程：

dp[i]=dp[i-3]+dp[i-2]+dp[i-1]

最后我们分析一下边界情况，分别在3,2,1,0位置取到。

代码实现：

class Solution 
{
public:int waysToStep(int n) {const int MOD=1e9+7;//创建dp表vector<int> dp(n+1);//处理边界条件：if(n==1)return 1;if(n==2)return 2;if(n==3)return 4;//初始化dp[0]=0;dp[1]=1;dp[2]=2;dp[3]=4;for(int i=4;i<=n;i++){dp[i]=((dp[i-3]+dp[i-2])%MOD+dp[i-1])%MOD;}return dp[n];}
};

最小花费爬楼梯

来源：最小花费爬楼梯

本题要小心一点的是：
楼顶是在整个数组外面而不是数组的最后一个位置。
每次爬楼梯只能爬一层或者两层。

本题在确定状态表示，我们还是根据经验，不过这道题当时咱们用了两种办法：

1.以i位置为结尾
2.以i位置为开始

以i位置为结尾：
状态表示：

dp[i]表示：以i位置为结尾时，的最小花费

状态转移方程：
首先，到达i位置有两种情况：
在这里插入图片描述
我们根据最近的一步来划分问题：

因此，状态转移方程：

dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

边界情况在0位置和1位置。

第二种方法这里就不再解释了。

代码实现：

class Solution 
{
public:int minCostClimbingStairs(vector<int>& cost) {//创建dp表int n=cost.size();vector<int> dp(n+1);//初始化dp[0]=dp[1]=0;//填表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];        }
};

解码方法：

来源：解码方法

对于本题而言就是：

dp[i]表示：以i位置为结尾时，解码方法的总数

在推方程之前，我们先画一下解码的情况：
在这里插入图片描述
分为单独解码和与前一个位置一起解码两种情况：

而单独解码和一起解码又要分为两种情况，成功和失败。
为什么会失败呢？
举个例子：

2和5可以一起解码，也可以分开解码，但到0位置时，就会解码错误，自己单独不能解码，要是与后面的6结合，
在这里插入图片描述
会出现之前说的前导0情况，也会解码错误。

因此，本题的状态转移方程为：

dp[i] = dp[i-1]+ dp[i-2]

3.初始化

本题初始化要在下标为0位置与下标为1位置进行初始化：
在这里插入图片描述

  dp[0]=s[0]!='0';//处理边界条件：if(n==1)return dp[0];if(s[0]!='0'&&s[1]!='0')dp[1]+=1;//前两个位置所表示的数：int t=(s[0]-'0')*10+s[1]-'0';if(t>=10&&t<=26)dp[1]+=1;

4.填表顺序

根据状态转移方程，我们计算dp[i]位置的值需要i-1与i-2位置的值，因此我们的填表顺序为：从左往右

5.返回值

我们要解码到最后一个位置，因此：返回dp[n-1]

代码实现：

class Solution 
{
public:int numDecodings(string s) {// 1.创建dp表// 2.初始化// 3.填表// 4.返回值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]+=1;//前两个位置所表示的数：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];}
};

斐波那契数

来源：斐波那契数

本题很简单，递推式题目都给了，直接上代码：

class Solution 
{
public:int fib(int n) {//创建dp表vector<int> dp(n+1);//处理边界条件：if(n==0)return 0;if(n==1)return 1;//初始化dp[0]=0;dp[1]=1;//填表for(int i=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
};