动态规划-矩阵中的最短路径

一、牛客 NC59 矩阵的最小路径和

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

数据范围: 1≤n,m≤500，矩阵中任意值都满足 0 ≤ a(i,j) ≤100 要求：时间复杂度 O(nm)O(nm)

例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12， 所选择的最小累加和路径如下图所示：

public int minPathSum (int[][] matrix) {
          
   
    int[] dp = new int[matrix[0].length];
    dp[0] = matrix[0][0];
    for(int i = 1; i < matrix[0].length; i++){
          
   
        dp[i] = dp[i-1] + matrix[0][i];
    }
     
    for(int i = 1; i < matrix.length; i++){
          
   
        for(int j = 0; j < dp.length; j++){
          
   
            if(j == 0){
          
   
                dp[j] = dp[j] + matrix[i][j];
                continue;
            }
            dp[j] = Math.min(dp[j], dp[j-1]) + matrix[i][j];
        }
    }
    return dp[dp.length - 1];
}

或者

public int minPathSum (int[][] matrix) {
          
   
    int m = matrix.length;
    int n = matrix[0].length;
    int dp[][] = new int[m][n];
    for(int i=0;i<m;i++){
          
   
        for(int j=0;j<n;j++){
          
   
            if(i==0&&j==0){
          
   
                dp[0][0]=matrix[0][0];
            }else if(i==0){
          
   
                dp[i][j] = matrix[i][j] + dp[i][j-1];
            }else if(j==0){
          
   
                dp[i][j] = matrix[i][j] + dp[i-1][j];
            }
            else{
          
   
                dp[i][j]= matrix[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    return dp[m-1][n-1];
}

二、最短路径

给定一个矩阵，从上到下找到最短路径, 第一行任意位置开始，只能往下走（包含对角线）

矩阵： {1, 3, 5, 9}, {8, 1, 3, 4}, {5, 0, 6, 1}, {8, 8, 4, 0} 结果输出: 6 解析： 因为路径1->1->0->4 为最短路径， {1, 3, 5, 9}, {8, 1, 3, 4}, {5, 0, 6, 1}, {8, 8, 4, 0} 变化过程为： [1, 3, 5, 9] [9, 2, 6, 9] [7, 2, 8, 7] [10, 10, 6, 7]