蓝桥杯必备——动态规划“路径问题”以及这种题的小结_蓝桥杯动态规划

回顾java数组部分知识

int[][]m=new int[2][3] 表达的含义是,两行，三列。

一、不同路径

不同路径

首先这个题我们分五步走

1.状态表示（按照经验+题目要求）

一般都是以···为结尾或者以···为起始

这道题我们就以dp[i][j]为他要求的到达结尾有多少条路径

此时你要思考一个东西，有多少条路径，他是怎么来的来考虑第二个状态转移方程。

2.状态转移方程

3.初始化

初始化我们采用相当于取巧的一个方式，采用虚拟节点，我们看到上面的状态转移方程，可能就思考一件事，我们会不会出现越界现象，比如最上面的那几个，无法进行-1操作的。

所以我们用虚拟节点，给你包一下，目的是不让他产生越界，红色的都是虚拟的

但是我们使用虚拟节点是有规则的：

1.虚拟节点里面的值，需要保证后面填表是正确的。

那么来思考一下，怎么虚拟节点的格子怎么处理呢，首先你要清楚一件事情，假如只有起点，也就是1*1，那么是不是只有一种，所以要保证起点是1，那么假如是1*2，1*3，是不是也只有一种走法，就是从起点一直向右走，那么再来想出现2*1，的话是不是起点只能往下走，也就只有一种走法，以此类推，所以只需要保证dp[0][1]=1或者dp[1][0]=1，二者不可都为1啊

2.下标的映射，原先表和这个表的对应关系

4.填表顺序

从上倒下，从左到右，

5.返回值

dp[i][j]

最后代码之前，给大家整一下数组，

double[]mark=new double[5],其中的下表是0，1，2，3，4。

这是对应的完整代码

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+1;i++){
     for(int j=1;j<n+1;j++){
     dp[i][j]=dp[i-1][j]+dp[i][j-1];
     }
}
return dp[m][n];
 
    }
}

二、不同路径II

不同路径II

这个题也是一样五步走，

1.状态表示（按照经验+题目要求）

一般都是以···为结尾或者以···为起始

这道题我们就以dp[i][j]为他要求的到达结尾有多少条路径

此时你要思考一个东西，有多少条路径，他是怎么来的来考虑第二个状态转移方程。

2.状态转移方程

还是我们的那个dp[i][j]=d[i-1][j]+dp[i][j-1],但是这个题和上一个题有区别，就是这个题多个障碍物，我们该如何处理这个障碍物呢？

我的刚开始做的时候很迷惑，在想这个障碍物改咋整，假如他不是我的终点，但是他又正好在经过终点的路上。其实这是我思维的一个误区，因为我其实已经选定好从结尾开始看了。

从结尾看就两种情况：

1.障碍物在终点处：在终点，肯定就到不了，就是0呗

2.障碍物不在终点：不在终点就是要想，他正常是左边的+上面的，遇到障碍物就和上面一样，视为0即可

3初始化：和上面一样。

4.填表顺序

从上倒下，从左到右，

5.返回值

dp[i][j]

这里在引入一个小知识

(int[][] ob) {

int m=ob.length,n=ob[0].length;

当二维数组的时候，m表示二维数组的列，n表示行数

class Solution {
    public int uniquePathsWithObstacles(int[][] ob) {
     int m=ob.length,n=ob[0].length;
     int[][]dp=new int[m+1][n+1];
     dp[0][1]=1;
     for(int i=1;i<m+1;i++){
         for(int j=1;j<n+1;j++){
//这里容易产生一个误区，考虑原来数组是0的部分，我刚开始是考虑1的所以导致想不明白假如我是1，我给障碍物赋值为0，问题障碍物本身就0。
//然后看一眼题解，发现是把没有石头的部分，去那么算
             if(ob[i-1][j-1]==0){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
             }
            
         }
     }
return dp[m][n];
    }
}

class Solution {
    public int uniquePathsWithObstacles(int[][] ob) {
     int m=ob.length,n=ob[0].length;
     int[][]dp=new int[m+1][n+1];
     dp[0][1]=1;
     for(int i=1;i<m+1;i++){
         for(int j=1;j<n+1;j++){
             if(ob[i-1][j-1]==1){
//我按照我的想法来一遍，发现不是误区，其实也是对的，只是说，这个需要赋值为0（不写赋值也可）之后，就要跳到下一个，不然的话，他就相当于没有障碍物了
                 dp[i][j]=0;
                 continue;
             }
             dp[i][j]=dp[i-1][j]+dp[i][j-1];
         }
     }
return dp[m][n];
    }
}

三、珠宝最高价值

珠宝

他和上面的区别，就是他的内部是有自己的数字的，所以我们需要算出来可以拿的最大价值。

1.状态表示：

dp[i][j]:表示在ij位置，获取到的最高价值，

2.状态转移方程

dp[i][j]=MAX(dp[i-1][j],dp[i][j-1])+frame[i][j];       左边和上边，看哪个更大，则说明有更高的价值，再加上当前这个地方的价值就构成了得到的最高价值。

3.初始化

初始化-还是防止越界问题，要出现虚拟节点

只有保证虚拟节点都是0，才不会导致，周围的受到影响，因为他是求的最大值，所以0不会收到影响

4.填表的顺序，从左到右，从上到下。

5.返回值dp[i][j]

class Solution {
    public int jewelleryValue(int[][] frame) {
  int m=frame.length,n=frame[0].length;
  int [][]dp=new int[m+1][n+1];
   for(int i=1;i<m+1;i++){
      for(int j=1; j<n+1;j++){
          dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])+frame[i-1][j-1];
      }
   }
  
  return dp[m][n];
    }
}

四、下降路径最小和

下降路径最小和

1.状态表示

用经验得到

dp[i][j]以i,j位置结尾的下降路径最小和

2。状态转移方程(这里说一下，你的状态方程是根据你的选择的点想法去处理的。

dp[i][j]=min(dp[i-1][j],dp[i-1][j+1],dp[i-1][j+2])+m[i][j]    （这个位置是最左边）

dp[i][j]=min(dp[i-1][j],dp[i-1][j],dp[i-1][j+1])+m[i][j]      （这个就是中间的）

3.初始化

初始化是根据你的状态转移方程决定的

假如说你的这个最左边（红色的是添加的虚拟节点）

中间的话就是这样需要

填表顺序：从上到下，从左到右

返回值：min(dp[i][j-1],dp[i][j],dp[j+1])

 
class Solution {
    public int minFallingPathSum(int[][] matrix) {
    int m=matrix.length,n=matrix[0].length; 
    int [][]dp=new int[m+1][n+2];
    for(int i=1;i<m+1;i++){
        dp[i][0]=Integer.MAX_VALUE;
        dp[i][n+1]=Integer.MAX_VALUE;
    }
    for(int i=1;i<m+1;i++){
        for(int j=1;j<n+1;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=Integer.MAX_VALUE;
for(int j=1;j<n+1;j++){
ret=Math.min(ret,dp[m][j]);
}
return  ret;
    }
}

最后总结

刷半天题，我感觉动态规划就像是说，你玩超级马里奥，从你通关的角度看，假如说往回看，你发现你通关了，其中你发现掉进水管子也能通关，但是掉进水管子是特殊情况，怎么说呢，就想是，你看到特殊情况了，但是他也是你的计划中的一员