专题十八_动态规划_斐波那契数列模型_路径问题_算法专题详细总结

目录

动态规划

动态规范五步走：

1. 第 N 个泰波那契数（easy）

解析：

1.状态表达式：

2.状态转移方程：

3.初始化：

4.填表顺序：

5.返回值

编写代码：

总结：

2. 三步问题（easy）

解析：

总结：

3. 使⽤最⼩花费爬楼梯（easy）

解析：

总结：

4. 解码⽅法（medium）

解析：

方法一：

优化：

总结：

路径问题

5. 不同路径（medium）

解析：

1.状态表达式：

2.状态转移方程：

3.初始化：

4.填表方向：

5.返回值：

编写代码：

总结：

6. 不同路径II（medium）

解析：

总结:

7. 礼物的最⼤价值（medium）

解析：

总结：

8. 下降路径最⼩和（medium）

解析：

总结：

9. 最⼩路径和（medium）

解析：

总结：

10. 地下城游戏（hard）

解析：

1.状态表达式：

2.状态转移方程：

这里考虑两种情况：

3.初始化：

4.填表顺序：

5.返回值：

代码编写：

总结：

独立解决一道困难题真的很帅好吧，xdm 给点鼓励~！！！

总结一下吧~总结不易，本章节对我的收获巨大，希望对你也是~！！！

---

动态规划

经过前面的优选算法，也算是一步步走到现在，前面学过了双指针、滑动窗口、二分、模拟、dfs、bfs等等一些列小的算法专题，有了很多不一样的收获和感悟。学到现在，有了一个新的总结体会：学完不总结，等于白学。所以要经常回顾和总结，时不时回头看看来时的路，学的越多忘的越多，一定要时刻回顾、回顾、再回顾！！！

接下来，我们就要进入动态规划专题，开启一篇更难更需要勇气来翻越的一座大山，但我们不能畏惧，而要鼓起勇气，向着这座高峰进发，去征服它，去领略那山顶上更为壮丽的风景。

最后：

所有计算机里的东西只不过都是人想出来的罢了，我们现在不知道，不代表我们未来不明白，我们只是还没学到，总有一天我会学到计算机里面的所有知识，scanf()不过也只是一个函数而已，只是我们还没有来得及去看它的源码，总有一天，我们会明白scanf()里面的一切；

动态规范五步走：

1.状态表达

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

后面的一切动态规划的题目，全部都是由这五步得来，里面最重要的就是：
状态表达式和状态转移方程

1. 第 N 个泰波那契数（easy）

解析：

这题很温柔，上来就直接把状态转移方程给我们了，但是我们还是要从0开始，来一步步推出状态表达式和状态转移方程：

1.状态表达式：

1）所谓动态规划就是要先构建一个dp表，然后根据经验+题目要求来总结出dp表内的每一个小格子代表的是什么含义；

2）分析问题的过程中，来发现重复的子问题

就如这道题，首先我们就设置一个线性dp表，来表示每个dp[i]->表示的是第N个泰波那锲数；

2.状态转移方程：

上面分析出了状态表达式，就是每个dp[i]->表示的是第N个泰波那锲数；

那么再有题目给出的T(n+3)=T(n)+T(n+1)+T(n+2)

那么在dp表中就可以推出：

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

3.初始化：

通过上面的状态转移方程可以看到，在一个for()内要是从0开始填表，那么就会有dp[i-3]这种越界的情况，所以，为了保证不会出现越界的情况我们就要从i==3开始填表，这样最小的数也都是dp[0]，那么我们就要在一开始就将dp[0]、dp[1]、dp[2]完成初始化；

根据题目要求：dp[0]=0，dp[1]=dp[2]=1;

4.填表顺序：

为了填当前位置的值：

那么我们就需要知道dp[i-3]这些值，就是在dp[i]的前面，所以我们只能先求出前面的值，才能再往后进行递归求解；

所以，填表顺序：从左往右；

5.返回值

题目要求+状态表示，因为每题题目不同，状态表达也不同，所以最后的返回值肯定也不同；

这一题要返回第N个泰波那契数，dp表又表示的是第i个泰波那契数，所以最后返回dp[n]即可；

编写代码：

class Solution {
public:int tribonacci(int n) {if(n==0||n==1) return n;if(n==2) return 1;//因为要返回dp[n] 就只能多开一个空间的大小，能够遍历到dp[n]vector<int> dp(n+1);dp[0]=0,dp[1]=dp[2]=1;for(int i=3;i<=n;i++)dp[i]=dp[i-3]+dp[i-2]+dp[i-1];return dp[n];}
};

总结：

动态规划的题目大体就是这么个流程，可能这题很简单，不能体现出它的强大，但是难的题目也是真的难；好好利用动态规划五步走，相信能够总结出自己的解题方法；

2. 三步问题（easy）

解析：

1.状态表达式：

2.状态转移方程：

由题目意思可以知道，dp[i]的值是i-1、i-2、i-3这三个位置都可以进行改变的，所以跟他们都有关系那么：

dp[i-1]就表示：到达i-1位置的上楼梯的总次数

dp[i-2]就表示：到达i-2位置的上楼梯的总次数

dp[i-3]就表示：到达i-3位置的上楼梯的总次数

所以dp[i]表示：到达i位置的上楼梯的总次数 = dp[i-1] + dp[i-2] + dp[i-3];

因为前三个位置都可以到达i位置，所以只要知道了前三个位置的次数，就可以得到i位置的总次数

3.初始化：

跟上题一样，这题为了防止越界访问数组，初始化任然是dp[i-3]、dp[i-2]、dp[i-1]三个位置的值；

        vector<int> dp(n+1);//初始化dp[0]=1,dp[1]=1,dp[2]=2;

4.填表顺序：

只有知道前面的值的结果，才能知道当前i位置的值，所以是从左往右进行填表；

5.返回值：

根据题目意思，返回dp[n] ，n位置的总次数，那么就要多开一个空间，防止遍历不到n位置

编写代码：

class Solution {
public:int waysToStep(int n) {if(n==0||n==1) return 1;if(n==2) return 2;vector<int> dp(n+1);//初始化dp[0]=1,dp[1]=1,dp[2]=2;for(int i=3;i<=n;i++){dp[i]=((dp[i-1]+dp[i-2])%1000000007+dp[i-3])%1000000007;}return dp[n];}
};

总结：

看到现在，这类动态规划其实也没有特别难，只要自己能够耐下心来一步步分析，真的就能够很容易的轻松解决掉这类问题；

3. 使⽤最⼩花费爬楼梯（easy）

解析：

1.状态表达式：

dp[i]表示：达到i位置所需要的最小费用

2.状态转移方程：

题目意思就是每次都可以从前一个阶梯或者前两个阶梯上来到达i位置：

那么每次上来都还要花费cost[i-1] 或者 cost[i-2] 位置的钱：

所以每次都取最小值，到达i位置：

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

所以每次dp[i] 都是由前面两个阶梯里面其中花费最小的一次得来的；

3.初始化：

题目说在0位置和1阶梯位置都不需要花费，所以dp[0] = dp[1] =0;

4.填表方向：

跟前面一样，也是要得到前面的值，才能往后继续填表，所以填表方向是从左往右填表；

5.返回值：

根据例子，有三个阶梯的花费，就要返回dp[3] ，那么n个就要返回dp[n],所以为了不越界，就要每次开n+1个位置，能够遍历到dp[n]

代码编写：

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();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];}
};

总结：

这一个小专题写起来完全一模一样，就是分析线性dp，然后考虑初始化和返回值即可；

4. 解码⽅法（medium）

题目意思还是很好懂的，就是有单独和双解码两种方式，单独解码，和跟前一个字符一起解码为一个字符，问一起有多少种解码方法

解析：

这里提供两种方法，第二种在第一种上的优化：

方法一：

1.状态表达式：

根据题目意思，表达dp[i]表示：以i位置为结尾，解码的总数；

2.状态转移方程：

所以dp[i] 分为两种情况下，分别加上解码成功下的上一个dp值；

这里求两个位置的解码和大于等于10，是因为只要s[i-1]这一位不为‘0’，就一定会大于10，否则就被解码成02、03这样就是错的；

3.初始化：

因为上面状态转移方程里面有i-2,所以循环要从n==2开始，所以要初始化dp[0]、dp[1]:

dp[0]=s[0]!='0';只要s的首字符不为0，那么就可以得到dp[0]=1;

dp[1]:

在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]++; 说明可以双解码，就又是一种解码方式；

4.填表方向：

从左向右；

5.返回值：

返回最后一位dp[n-1] 表示n-1位置的解码总数；

编写代码：

方法一：

class Solution {
public:int numDecodings(string s) {if(s[0]=='0') return 0;int n=s.size();vector<int> dp(n);if(s[0]!='0') dp[0]=1;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]++;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];}
};

优化：

我们可以看到这里初始化和循环内代码十分冗余，那么想想有没有办法可以简化一下初始化呢：

细节问题：

那么只需要将dp表多开一个空间，然后让dp[1]这个位置表示的是原来的dp[0]，那么就可以让现在dp[2]表示原来的dp[1]就可以把刚刚初始化dp[1]的那一大堆步骤放在循环内了；

现在我们给dp表多开了一个空间，就要考虑当前dp[0] 的位置填什么：

那么这个时候就要考虑循环内的dp[2],倘若dp[2]这个位置可以双解码：

说明dp[2] += dp[2-2]
即dp[2] += dp[0],如果这里dp[0]=0,那么就相当于没有加上，
所以dp[0]=1;

此时dp[1]就还是跟上面原来的dp[0]一样，查看dp[1]=s[0]!='0';

最后要处理的就是s字符串下标的问题，因为dp都往后移动了一位，所以遍历s的时候i都要-1：i-1

class Solution {
public:int numDecodings(string s) {if(s[0]=='0') return 0;int n=s.size();vector<int> dp(n+1);dp[0]=1; //保证后面的填表是正确的dp[1]=s[0]!='0';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];}
};

总结：

优化就是在普通解法下总结出来的，我们可以先尝试普通解法的思想，然后再去考虑优化，这样一步步来，肯定会成功的，加油！~

路径问题

5. 不同路径（medium）

解析：

1.状态表达式：

因为这一题是一个二维数组内求路径总数，所以确定位置就是要确定当前dp表的一个位置

dp[i][j]表示：以i，j结尾的位置的总路径总数；

2.状态转移方程：

这个位置可以由上和左方向走来，所以：
就是当前位置的路径数，就等于 上方向 和 左方向 两个方向走来的路径和

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

3.初始化：

由于再dp表原先[0,0]位置可能会存在越界的情况，所以我们要将整个dp表多加一列和一行，就是为了预防[i-1]，[j-1]这种情况；

所以就要考虑这多加的一行一列需要初始化为什么：

由于再[1，1]这个位置也需要由上一步得到当前的路径数，显然我们是从[1,1]开始的，那么路径是就是1，那么只需要将dp[0][1]或者dp[1][0]任意一个位置设置成1即可满足条件；

4.填表方向：

根据状态转移方程可以知道，都是要明白前面的值，才能继续往后填，所以填表方向就是从左往右，从上往下；

5.返回值：

根据状态表达式，明白dp[m][n] 就是再[m,n]这个位置的的路径总数，所以返回dp[m][n]

编写代码：

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1,0));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];}
};

总结：

整体来说还是非常好写的，这种思路很顺滑，如果真是自己一步步思考出来的还是非常有成就感的

6. 不同路径II（medium）

解析：

这题唯一跟上提不同的就是状态转移方程：

唯一的不同就是在考虑当前位置是否存在障碍物，如果是，那么当前位置的dp值就是0；否则dp就等于dp[i][j]=dp[i-1][j] + dp[i][j-1]

 

代码编写：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& ob) {int m=ob.size(),n=ob[0].size();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++)if(ob[i-1][j-1]!=1) dp[i][j]=dp[i-1][j]+dp[i][j-1];return dp[m][n];}
};

总结:

如果真的自己能够绕出来，真的贼有成就感，加油，一定会成功的！！！

7. 礼物的最⼤价值（medium）

解析：

1.状态表达式：

dp[i][j]表示：以i，j为结尾的位置上 ， 珠宝的最大价值总和；

2.状态转移方程：

因为每次只能选取一条路径上的最大珠宝价值，所以当前位置dp[i][j]就是上方向 或者 左方向取最大值然后加上当前位置的珠宝价值：

 dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];

3.初始化：

因为在dp[1][1]的位置上，当前位置的价值就只是最初始位置的珠宝价值，所以不需要外边界的值，那么外边界都初始化为0；

4.填表方向：

通过状态转移方程，可以知道只有把前面的值填完了，才能填当前的值，那么就是从左往右填，从上往下填；

5.返回值：

根据状态表达式，可以得到dp[m][n]表示在[m,n]位置结尾的最大珠宝总和；

代码编写：

class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {int m=frame.size(),n=frame[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1));int ret=0;for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];return dp[m][n];}
};

总结：

这题就是上面两题的变形，还是非常好想的，依旧是套着模板写题；

8. 下降路径最⼩和（medium）

解析：

1.状态表达式：

设置dp[i][j]表示：以i，j为结尾的时候，当前路径最小和；

2.状态转移方程:

这里状态转移方程就要考虑当前位置在边界情况下是否会越界的问题：

那么设置一个dp表，由状态表达式可以知道dp[i][j]表示：以i，j为结尾的时候，当前路径最小和；

那么当dp在第一行的时候，就要通过上面一行来求出最小值，但是这样会越界，就要多开一行，设置成0，来保证不会越界；这个时候，不但要多开一行，还要多开两列，将左右两列都设置成INT_MAX，因为本来这两列是不存在的，但是为了在遍历上一行的三个位置的时候会出现越界情况，所以，多开两列，设置成最大值，这样就不会出现越界和乱取值的情况，这样怎么取，都是在ma原数组里面的值；

所以状态转移方程就是：

dp[i][j]=min(min(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1])+ma[i-1][j-1];

通过上一行的三个位置取出最小值，然后加上当前位置的ma的大小；

3.初始化：

上面以及涉及到，就是将第一行全部初始化为0，左右两列都初始化为INT_MAX，为的就是数组不越界，和不乱取值

4.填表顺序：

根据状态转移方程可以看到，必须要知道上面的值，才能往下求，所以是从左往右，从上往下填表

5.返回值：

每条路径都会走到最后一行，那么只需要用ret来记录最后一行的最小值即可；

编写代码：

class Solution {
public:int minFallingPathSum(vector<vector<int>>& ma) {int m=ma.size(),n=ma[0].size();vector<vector<int>> dp(m+1,vector<int>(n+2));for(int i=0;i<=m;i++){dp[i][0]=INT_MAX;dp[i][n+1]=INT_MAX;}int ret=INT_MAX;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=min(min(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1])+ma[i-1][j-1];if(i==m) ret=min(dp[i][j],ret);}}return ret;}
};

总结：

只要画图一步步把每一步都分析清楚，那么就是按部就班的写代码就ok了

9. 最⼩路径和（medium）

解析：

这一题就不过多赘述，题目意思完全就是跟上面几题一模一样，唯一的不同就是初始化的不同：

如果这题我跟上面一样也全部都初始化为0，那么由状态转移方程就是:

dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i-1][j-1];

每次都是在左边和上面去一个较小值，然后加上当前位置的gird数组的数字，那么可以现象，外边界全是0，那么遍历在第一行和第一列的时候，怎么会加上左边或者上面的值呢，看到都是加上最小的0了，所以这种初始化是不成立的；

那么就有另外一种办法，全部初始化为INT_MAX,那么对于dp[1][1]进行计算的时候，就是取
dp[0][1] 和 dp[1][0]里面最小的一个再加上grid[0][0]，显然这是绝对不可以的，因为dp[1][1]这个位置就只是只应该有自己原本的那个数，所以dp[0][1] 和 dp[1][0]都应该初始化为0，其他位置都初始化为INT_MAX;

所以这一题就只有这一个初始化的位置需要注意；

代码编写：

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));dp[0][1]=0;for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i-1][j-1];cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;}return dp[m][n];}
};

总结：

写出一个动态规划的题目并不是一帆风顺，需要自己的独立思考和每一个位置不出现漏洞，所以对于每一步都要仔细的去分析分析在分析；

10. 地下城游戏（hard）

解析：

1.状态表达式：

这题如果按照前面一样正着来求解肯定会很麻烦，我们可以先尝试一下：

每次都要考虑骑士的血量，并且我们并不知道骑士的初始血量，所以每次都要给一个初始血量后再出发，知道走下去时血量为空或者还有更优解才会停下来，所以从数组的[0,0]位置开始行走的话一定会失败的；那么问题来了，考虑骑士的最初血量，我们就可以正难则反，从骑士救出公主的那一刻开始往回走，直到走到[0,0]这个位置停下来得到最少的血量即可；

所以

dp[i][j]表示：以i，j为结尾的骑士所需要的最少血量；

2.状态转移方程：

这里考虑两种情况：

第一种就是当最后一个格子是负数的时候；

第二种就是最后一个格子是正数的时候；

说明如果最后一个格子是负数，就要考虑在进入最后一个格子之前拥有的血量是要至少大于这个格子扣除血量+1的，也就是说，经过最后一个格子了，至少还剩最后一滴血；

如果最后一个格子是正数，那么就只需要进入之前至少还剩一滴血就ok了；

那么就说明dp[i][j]=下面 和 右边 取min后 然后减去du[i][j]的值即可；

如果du[i][j] 为负值，那么就正好减后成正值；

如果du[i][j] 为正值：此时dp[i][j]>0

所以状态转移方程：

                int sum=min(dp[i+1][j],dp[i][j+1]);

                if(du[i][j]>0&&du[i][j]>=sum) dp[i][j]=1;

                else dp[i][j]=sum-du[i][j];

3.初始化：

根据上面的图和分析可以得出，为了在边界条件下不会越界和乱取值，只用初始化一个值即可就

dp[m][n-1]=1;

4.填表顺序：

这次填表顺序很不一样，因为我们是要从后往前遍历，一直得到dp[0][0],所以填表顺序就是从下往上，从右往左；

5.返回值：

根据状态表达式，返回dp[0][0] 即可表示在[0,0]位置骑士所需要的最少血量；

代码编写：

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& du) {int m=du.size(),n=du[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));dp[m][n-1]=1;for(int i=m-1;i>=0;i--){for(int j=n-1;j>=0;j--){int sum=min(dp[i+1][j],dp[i][j+1]);if(du[i][j]>0&&du[i][j]>=sum) dp[i][j]=1;else dp[i][j]=sum-du[i][j];}}return dp[0][0];}
};

总结：

独立解决一道困难题真的很帅好吧，xdm 给点鼓励~！！！

总结一下吧~总结不易，本章节对我的收获巨大，希望对你也是~！！！