系统学习算法：动态规划（斐波那契+路径问题）

题目一：

思路：

作为动态规划的第一道题，这个题很有代表性且很简单，适合入门

先理解题意，很简单，就是斐波那契数列的加强版，从前两个数变为前三个数

算法原理：

这五步可以说是所有动态规划的通用步骤，基本按照这个逻辑步骤，正确地完成每一个步骤，最后就能得到正确结果

1.状态表示：

基本所有的动态规划都要先创建一个dp表，也就是一维数组或者二维数组，而这个数组中的每一个空对应的含义就是状态表示

像本道题，我们要创建一个一维数组，而数组下标n对应的值就应该为第n个泰波那契数，这个状态表示就是我们所定义的，这个是最重要的一步，跟之前递归专题的定义递归函数功能是一样的，你想怎么定义就怎么定义，这道题很明显这么定义就很符合第一反应，因此这就完成了动态规划的第一步，状态表示

2.状态转移方程

用人话来说就是靠这个方程将dp表所有给填满，而这一步就是动态规划最难的一步，这道题题目已经给出了状态转移方程，那就是dp[n]=dp[n-1]+dp[n-2]+dp[n-3]，所以我们就是根据这个状态转移方程去填这个dp表，当然其他动态规划题就不会像本题一样简单，就需要自己去推导状态转移方程

3.初始化

其实就跟数独一样，题目得先给你一些存在的数，你才能去填其他的空，不能什么都不给，就让你填，而初始化就是先填上一部分dp表的空，然后状态转移方程通过初始化的值去填剩下的空

本题就是给了前三个泰波那契数0，1，1，这样我们才能通过状态转移方程往后推出更多的泰波那契数

同时也这一步也用于避免填表时越界的问题，比如当n<=2时，根据状态转移方程，就会出现访问-1，-2下标的值，就越界了，所以我们需要对这些进行特判

4.填表顺序

其实就是从左往右填，还是从右往左填，这道题很明显是根据前面三个泰波那契数推导当前的泰波那契数，根据状态表示，也就是数组靠前的是前面的泰波那契数，因此就是从左往右填

5.返回值

dp表填完后，那就该返回答案了，根据状态表示，确定返回值，比如本题状态表示是下标为n的代表第n个泰波那契数，那么题目要求我们返回第n个泰波那契数，那么我们就返回下标为n的就可以了，这时题目也就解决了

代码1：

class Solution {public int tribonacci(int n) {//初始化加特判if(n<=2){if(n==0){return 0;}else{return 1;}}int[] dp=new int[n+1];dp[0]=0;dp[1]=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];}
}

而这道题和后面的背包问题可以使用空间优化的方法，也就是滚动数组

我们可以发现有些数用完其实就没用了，就像一次性筷子一样，那么用完就该扔了，同理我们的数组其实就没必要继续保留那些用过的值了

像我们这道题，就只用4个变量，就可以解决了，abc代表前三个泰波那契数，d表示当前的泰波那契数，然后到下一个泰波纳锲数时，通过滚动的操作，将上一回的bcd赋给abc，然后再求出d，如此类推

这样我们的时间复杂度就从原来的O（N）变为O（1），所以这种办法可以降下一个指数级别的复杂度

代码2（空间优化）：

class Solution {public int tribonacci(int n) {//初始化加特判if(n<=2){if(n==0){return 0;}else{return 1;}}int a=0,b=1,c=1,d=0;for(int i=3;i<=n;i++){//状态转移方程d=a+b+c;//滚动数组a=b;b=c;c=d;}//返回值return d;}
}

题目二：

思路：

题意很简单，就是每次可以有3种跳台阶的选择，然后返回到某一阶台阶有多少种跳法 

以n=3为例，小孩从第0阶为出发点，可以选择（1，2，3）每次跳1步到达第3阶，也可以选择（1，3）第一次跳1步，第二次跳2步到达第3阶，也可以选择（2，3）第一次跳2步，第二次跳1步到达第3阶，还可以选择直接跳3步到第3阶

总共4种跳法，所以返回4

算法原理：

还是按照动态规划的五个步骤走

1.状态表示：

dp表的第i个下标表示到达第i阶有多少种跳法

2.状态转移方程：

因为有3种跳法，所以如果要到第i阶，只能从i-3阶，i-2阶，i-1阶分别跳3步，2步，1步才能到达第i阶，而dp[i-3],dp[i-2],dp[i-1]记录着到达对应台阶的跳法，因此状态转移方程为dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

3.初始化：

因为有三种跳法，所以至少要初始化前3个台阶，易知dp[1]=1,dp[2]=2,dp[3]=4，所以初始化这三个值然后并进行特判

4.填表顺序：

从低台阶跳到高台阶，而dp表前面的值记录的低台阶的跳法，后面的就记录更高台阶的跳法，所以填表顺序是从左往右填

5.返回值：

因为状态表示中dp[i]表示第i阶有多少种跳法，所以第n阶有多少种跳法要返回dp[n]，问题就解决了

代码：

class Solution {public int waysToStep(int n) {//初始化并且特判if(n==1||n==2){return n;}if(n==3){return 4;}//求模数，e代表科学计数法，且默认为double类型int mod=(int)1e9+7;int[] dp=new int[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];}
}

其实这道题跟上面那道题几乎一模一样，因此也可以用滚动数组进行空间优化，就不多说了

题目三：

思路：

题意也很简单，就是可以选择跳1步还是跳2步，然后每次跳完要给钱，找到最小花费的值，唯一需要注意的是终点并不是最后一个元素，而是最后一个元素的后面，也就是数组越界的位置

算法原理：

 还是五个步骤

1.状态表示

一般都是以dp表的第i个位置，表示题目的要求，本题那就是dp[i]就表示，到达第i阶时所需要的最少花费

2.状态转移方程

一般根据dp表之前的填空情况来推导当前填表的答案，dp[i]表示第i阶时所需要的最少花费，那么如果要到第i阶，那么就只能从第i-1阶或者i-2阶开始跳，如果要求第i阶时所需要的最少花费，那么就从第i-1阶或者i-2阶的最少花费再加上对应的花费选较少的那个，而第i-1阶或者i-2阶的最少花费又是由dp[i-1]和dp[i-2]记录，因此就形成了闭环

所以状态转移方程：dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

3.初始化

题目说可以从0下标和1下标开始跳，那么所以dp[0]=dp[1]=0，避免了当i过小时数组越界

4.填表顺序

还是从下往上跳，那么dp表左边的指向低台阶，dp表右边指向高台阶，高台阶的最少花费由低台阶的最少花费决定，所以填表顺序是从左往右

5.返回值

因为最后要跳出数组，所以要返回dp[n]，因此dp表在创建的时候要多创一个位置new int[n+1]

问题就解决了

代码1：

class Solution {public int minCostClimbingStairs(int[] cost) {//初始化int n=cost.length;int[] dp=new int[n+1];dp[0]=dp[1]=0;//状态转移方程for(int i=2;i<=n;i++){dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}//返回值return dp[n];}
}

同理也可以逆向思考

刚刚的状态表示是dp[i]为到第i阶的最少花费，那么也可以反过来，dp[i]为从第i阶为起点，到顶的最少花费，那么初始化也是先初始dp[n-1],dp[n-2]，填表顺序也变为从右往左，返回值则是dp[0]和dp[1]的最小值

代码2：

class Solution {public int minCostClimbingStairs(int[] cost) {//初始化int n=cost.length;int[] dp=new int[n];dp[n-1]=cost[n-1];dp[n-2]=cost[n-2];//状态转移方程for(int i=n-3;i>=0;i--){dp[i]=Math.min(dp[i+1],dp[i+2])+cost[i];}//返回值return Math.min(dp[0],dp[1]);}
}

题目四：

 思路：

题意不是很难理解，就是返回一段字符串有多少种解码方法

需要注意的就是6是合法解码方式，06不是合法解码方式，最大解码为26，如果有一处出现了无法解码，那么整条解码方法就为0

算法原理：

还是五个步骤：

1.状态表示 

一般都是以某一个位置为起点或结尾+题目要求，本题就以i位置为结尾，有多少种解码数

2.状态转移方程

根据题意我们可以知道，要么是单独解码，要么是连续两个一起解码

这时就开始分类讨论

如果是单独解码，如果不为0，那么此时解码数就加上前一个位置的解码数，如果为0，那就不能单独解码，就不加上前一个位置的解码数，但也不能直接就认为解码失败，因为还有连续解码的情况，比如10，20

然后是连续解码，如果与前一个位置连起来在10-26之间，那么就说明能被连续解码，这时前一个位置和当前位置就成为了一个整体，因此加上的是i-2位置的解码数，反之，不在10-26之间就不加i-2位置的解码数

因为我们状态表示是以i位置为结尾，所以我们只用分析与前一个位置的连续解码情况，而不用管后面的位置

所以总体来说状态转移方程为

dp[i]+=dp[i-1]（单独解码如果成功）+dp[i-2]（连续解码如果成功）

3.初始化

为了避免越界情况，所以至少要先初始化dp[0]和dp[1]

dp[0]前面没有元素，那么只能单独解码，所以如果是0就为0，不是0就为1

dp[1]前面有dp[0]，所以可以单独解码也可以连续解码，同理单独解码时如果是0就不加，不是0就加1，连续解码时如果为10-26就加1，不是就不加

4.填表顺序

因为是以i位置为结尾，所以是根据前面填好的情况来填后面的空，因此是从左往右

5.返回值

因为要返回整个解码总数，所以是以n-1位置为结尾有多少解码方法，而状态表示以i位置为结尾，有多少种解码数，所以就返回dp[n-1]

代码1：

class Solution {public int numDecodings(String s) {//初始化int n = s.length();int[] dp = new int[n];char[] ch = s.toCharArray();//特判dp[0]和dp[1]if (ch[0] != '0') {dp[0] = 1;}if (n == 1) {return dp[0];}//单独解码if (ch[0] != '0' && ch[1] != '0') {dp[1] += 1;}//连续解码int num = (ch[0] - '0') * 10 + (ch[1] - '0');if (num >= 10 && num <= 26) {dp[1] += 1;}//状态转移方程for (int i = 2; i < n; i++) {//单独解码if (ch[i] != '0') {dp[i] += dp[i - 1];}//连续解码int num = (ch[i - 1] - '0') * 10 + (ch[i] - '0');if (num >= 10 && num <= 26) {dp[i] += dp[i - 2];}}//返回值return dp[n - 1];}
}

可以发现在初始化特判的时候非常冗杂，甚至比状态转移方程写的还多，而其中dp[1]的初始化流程和状态转移方程几乎一致，因此能不能直接将dp[1]的初始化流程放到状态转移方程中完成，当然是可以的

这里就用到了有些动态规划题目可以采用虚拟节点的方法进行初始化

就是多创建一个空，然后所有往后移动一位

dp[1]就是原来的dp[0]，那么还是只有单独解码的可能，因此是0就为0，不为0就为1，然后dp[2]就是原来的dp[1]，根据状态转移方程 

dp[i] = dp[i-1]（单独解码如果成功）+dp[i-2]（连续解码如果成功）

所以此时dp[2-2]应该设置为1，因为如果能连续解码，那么就加1，因此虚拟节点就初始化为1，如果连续解码不成功，那么就根本用不到dp[2-2]，无所谓dp[2-2]的值，所以综上要将dp[0]初始化为1

代码2：

class Solution {public int numDecodings(String s) {//初始化int n = s.length();int[] dp = new int[n+1];char[] ch = s.toCharArray();//dp[0]和dp[1]dp[0]=1;if (ch[0] != '0') {dp[1] = 1;}//状态转移方程for (int i = 2; i <= n; i++) {//单独解码if (ch[i-1] != '0') {dp[i] += dp[i - 1];}//连续解码int num = (ch[i - 2] - '0') * 10 + (ch[i-1] - '0');if (num >= 10 && num <= 26) {dp[i] += dp[i - 2];}}//返回值return dp[n];}
}

题目五：

思路：

之前在记忆化搜索的章节做过这道题，因为记忆化搜索和动态规划其实大差不差，因此也可以用动态规划做

算法原理：

这道题因为涉及了二维表，与之前一维表有些不一样，但步骤都是那五步

1.状态表示

 因为是二维表，那么就是以dp[ i ][ j ]为结尾，加上题目要求，到达ij位置时的路径和

2.状态转移方程

因为只能向右或向下，所以到达该位置时，只能从上面到下面，从左边到右边，因此状态转移方程

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

3.初始化

因为处于最左边和最上边的边界格子，在状态转移方程中会越界，所以要对此进行特殊处理，而在一维中是采用多开一个位置，即虚拟节点，而在二维中，往往会在左边多开一列，上边多开一行，那么边界情况就全部解决了，不会越界，而在起点dp[1][1]应该为1，所以可以直接给dp[1][1]赋值为1，也可以在dp[0][1]或者dp[1][0]赋值为1，然后dp[1][1]再通过状态转移方程赋值为1，都是可以的

4.填表顺序

因为是根据上边和左边来决定当前位置，因此应该是从上往下，且从左往右填表的

5.返回值

dp[ i ][ j ]表示为当前位置的路径和，题目要求返回到达终点有多少种不同路径，那么我们就返回dp[m][n]即可

代码：

class Solution {public int uniquePaths(int m, int n) {//初始化int[][] dp=new int[m+1][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];}
}

题目六：

思路：

跟上一道题几乎一模一样，就是多了障碍物这个设置

算法原理： 

还是五个步骤，除了状态转移方程与上一题不太一样，其他都一样

因为出现了障碍物，所以这个格子的dp值一定为0，因此只需要在填表时判断一下是否有障碍物，如果有就直接设为0，如果不是障碍物，则继续套用上一题的状态转移方程

代码：

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {//初始化int row=obstacleGrid.length;int col=obstacleGrid[0].length;int[][] dp=new int[row+1][col+1];dp[0][1]=1;//状态转移方程for(int i=1;i<=row;i++){for(int j=1;j<=col;j++){if(obstacleGrid[i-1][j-1]==1){dp[i][j]=0;}else{dp[i][j]=dp[i-1][j]+dp[i][j-1]; }}}//返回值return dp[row][col];}
}

题目七：

思路：

还是路径问题，依然可以采用动态规划，题意很简单，就是从左上角为起点，右下角为终点，移动方向只能向下或向右，然后返回路径上的最大值

算法原理：

 依旧是五个步骤

1.状态表示

以i j位置为终点，到达这里的路径最大值

2.状态转移方程

因为只有向下和向右两个方向，那么能到达[i][ j ]位置的只能是[i-1][ j ]，或者[i][ j-1] ，而又要找到当前位置路径最大值，那么就选择这两格的最大值，再加上当前位置的值就是当前位置的最大值，因此状态转移方程是

dp[i][ j ]=Math.max(dp[i-1][ j ]，[i][ j-1]) + frame[i][ j ]

3.初始化

依旧多加一行多加一列，方便填表时不越界

4.填表顺序

根据移动方向可知，填表顺序是从上往下，从左往右

5.返回值

根据状态表示，返回dp[m][n]

代码：

class Solution {public int jewelleryValue(int[][] frame) {//初始化int row=frame.length;int col=frame[0].length;int[][] dp=new int[row+1][col+1];//状态转移方程for(int i=1;i<=row;i++){for(int j=1;j<=col;j++){dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];}}//返回值return dp[row][col];}
}

题目八：

思路：

依旧是路径问题，只是这回移动方向变成了只能向下，且左右可以对角移动，最后返回最小下降路径的值

算法原理：

依旧是五个步骤

1.状态表示

以i j位置为终点，表示到达此位置时的最小下降路径和

2.状态转移方程

因为方向多了对角线，且只能从上一行下来，因此为[i-1][ j-1 ]，[i-1][ j ]，[i-1][ j+1 ]

而要找的是最小的，所以就是状态转移方程为

dp[i][ j ]=Math.min(dp[i-1][ j-1 ]，Math.min(dp[i-1][ j ]，dp[i-1][ j+1 ]))

3.初始化

为了避免越界问题，所以依旧要扩容来将原数组包围，所以就是多加一行，但是这回就要多加两列，因为左边要有一列，右边要有一列，这样才能全部包围住，不会越界

因为要找最小的，所以扩容的位置的值不能初始化为0，不然会影响到真正的结果，因此要初始化为最大值

4.填表顺序

根据移动方向顺序，还是从上到下，从左往右

5.返回值

最后都会到达最后一行，所以只用返回最后一行的最小dp值即可

代码：

class Solution {public int minFallingPathSum(int[][] matrix) {//初始化int row=matrix.length;int col=matrix[0].length;int[][] dp=new int[row+1][col+2];for(int i=1;i<=row;i++){dp[i][0]=dp[i][col+1]=Integer.MAX_VALUE;}//状态转移方程for(int i=1;i<=row;i++){for(int j=1;j<=col;j++){dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i-1][j+1]))+matrix[i-1][j-1];}}//返回值int ret=dp[row][1];for(int j=2;j<=col;j++){ret=ret>dp[row][j]?dp[row][j]:ret;}return ret;}
}

题目九：

思路：

还是路径问题，只是变成要求最小值，其他的要求和之前珠宝那道题目几乎一样

算法原理：

依旧是五步：

1.状态表示

以i j位置为终点，表示到达此位置时的最小路径和

2.状态转移方程

因为只有向下和向右两个方向，那么能到达[i][ j ]位置的只能是[i-1][ j ]，或者[i][ j-1] ，而又要找到当前位置路径最小值，那么就选择这两格的最小值，再加上当前位置的值就是当前位置的最小值，因此状态转移方程是

dp[i][ j ]=Math.min(dp[i-1][ j ]，[i][ j-1]) + grid[i][ j ]

3.初始化

依旧多加一行多加一列，方便填表时不越界，只是这里要求最小值，所以扩容的位置要初始化为MAX，而从起点开始，因此它的上一格或者左一格任选一个初始化为0即可

4.填表顺序

根据移动方向可知，填表顺序是从上往下，从左往右

5.返回值

根据状态表示，返回dp[m][n]

代码：

class Solution {public int minPathSum(int[][] grid) {//初始化int row=grid.length;int col=grid[0].length;int[][] dp=new int[row+1][col+1];for(int j=2;j<=col;j++){dp[0][j]=Integer.MAX_VALUE;}for(int i=1;i<=row;i++){dp[i][0]=Integer.MAX_VALUE;}//状态转移方程for(int i=1;i<=row;i++){for(int j=1;j<=col;j++){dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];}}//返回值return dp[row][col];}
}

题目十：

 思路：

依旧是路径，题意也很好理解，跟游戏中打怪boss一样，正数表示为补给包，负数代表有怪物，0表示为空房间，每次只能选择进入右边的房间或者下边的房间，从左上角出发，到右下角结束，但过程中要保持有血量（路径和）要大于等于1，问一开始起点初始的最低血量

以示例1为例子，按照该路径走可以算出起始最低血量为7，但不要认为就是-2+-3+3+1+-5=-6，所以直接-6取反再加1就可以了，这里就容易出现一个误区，那就是这个-6是所有路径上所需血量的最小值，这道题刚好是最后一格是所有路径上的所需血量的最小值，所以是-6

如果还有疑惑，举个游戏中的例子就明白，你进入一个房间，遇到超级大怪兽，假设打倒需要10000血，然后打完这个怪兽后面有个房间有9999血的补给包，那这里你能直接

10000-9999+x(初始血量)>=1，x=2，能这样算嘛，你都打不过那个怪兽，后面补给包不可能拿到的

初始最低血量应该为10001滴血

算法原理：

依旧是路径问题，大致步骤也是一样的

但是从第一步就容易出错，根据之前的题目，我们状态表示都是以某个位置为结尾，怎么这么样，而这道题用以结尾这种状态表示则是错误的，因为具有“有后效性”

可以简单去尝试下，就是填dp表时，刚根据上左dp值得出当前dp值，但是后面依然会影响当前dp值

如上图，假设设置状态表示为到达ij位置时，所需最低初始健康点数

那么-2这个格根据上左扩容的dp就应该为3，到了-3这个格子，发现最低应该是6，3这个格子为6，然后到3这个格子，你就不知道怎么填了，因为你不能6-3就填3吧，那就犯了一开始的误区，也不能不管仍然填6吧，那后面就完全乱套了，最后返回-5这个格子的dp值肯定是错的，这就是被后面的状态给影响了，也就是“有后效性”

简单来说还是被后面的血包影响了，以为你能欠血后面再还，实际是全程都不能低于1

因此就需要改变状态表示，反正不是以结尾，就是以起点

1.状态表示

以i j为起点，所需最低初始健康点数

2.状态转移方程

因为是以起点，那么就需要根据后面的dp值来填，即右格和下格的dp值

因为要找最低的，所以是用右格和下格的min，然后再减去当前格子dungeon的值，也就是dp值

当然因为dungeon有可能为正数（血包），所以减去后有可能为负数，此时又犯了欠血的误区，因此要if判断一下，如果为负数，那么就直接修改为1，因为至少需要活着

所以状态转移方程为

dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];

                if(dp[i][j]<=0){

                    dp[i][j]=1;

                }

3.初始化

为了避免越界问题，所以要将原数组包围起来，因此要多加一行多加一列，但只用包越界的那边，因为这次是向右和向下，所以围的是右边和下边

因为要找最小值，所以应该初始化为MAX，因为终点下右的都是初始化的，所以要任选一个更改为1，表示最低需要1滴血

4.填表顺序

如果状态表示是以起点，那么填表顺序就反过来了，从下往上，从右往左

5.返回值

根据状态表示返回第一格的dp就是

代码：

class Solution {public int calculateMinimumHP(int[][] dungeon) {//初始化int row=dungeon.length;int col=dungeon[0].length;int[][] dp=new int[row+1][col+1];for(int i=0;i<=row;i++){dp[i][col]=Integer.MAX_VALUE;}for(int j=0;j<=col;j++){dp[row][j]=Integer.MAX_VALUE;}dp[row-1][col]=1;//状态转移方程for(int i=row-1;i>=0;i--){for(int j=col-1;j>=0;j--){dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];if(dp[i][j]<=0){dp[i][j]=1;}}}//返回值return dp[0][0];}
}