矩阵的最小路径和_

Java

chenyd

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param matrix int整型二维数组 the matrix

* @return int整型

*/

public int minPathSum (int[][] matrix) {

// write code here

//dp[m][n]表示走到m,n的最小加和

//转移方程为f[m,n]=min{f[m-1,n],f[m,n-1]}+matrix[m][n]

int [][]dp = new int[matrix.length][matrix[0].length];

dp[0][0] = matrix[0][0];

for (int i = 0; i < matrix.length; i++) {

for (int j = 0; j < matrix[0].length; j++) {

if (i - 1 < 0 && j - 1 < 0) {

dp[i][j] = matrix[i][j];

} else if (i - 1 < 0) {

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

} else if (j - 1 < 0) {

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

} else {

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

}

return dp[matrix.length - 1][matrix[0].length - 1];

}

发表于 2023-07-19 18:15:59 回复(0)

Java

做则必成的勇气和信心

 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[i][j]=matrix[i][j];
                }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]=Math.min(dp[i-1][j]+matrix[i][j],dp[i][j-1]+matrix[i][j]);
                }
            }
        }
    return dp[m-1][n-1];
    }

发表于 2023-07-11 16:29:47 回复(0)

Java

Zhima1234

public class Solution {
    public int minPathSum (int[][] matrix) {
        int height = matrix.length;
        int width = matrix[0].length;
        // 从[0,0]到[i,j]的最小路径和
        int[][] dp = new int[height][width];
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < height; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }
        for (int j = 1; j < width; j++) {
            dp[0][j] = dp[0][j - 1] + matrix[0][j];
        }
        for (int i = 1; i < height; i++) {
            for (int j = 1; j < width; j++) {
                dp[i][j] = Math.min(
                               // 从上边向下
                               dp[i - 1][j] + matrix[i][j],
                               // 从左边向右
                               dp[i][j - 1] + matrix[i][j]
                           );
            }
        }
        return dp[height - 1][width - 1];
    }
}

发表于 2023-05-31 10:07:38 回复(0)

Java

牛客839384289号

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

发表于 2023-03-23 00:28:40 回复(0)

Java

键盘都敲坏了.

public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // 行数
        int i = matrix.length;
        // 列数
        int j = matrix[0].length;
        // 初始化表格
        int[][] table = new int[i][j];
        // 首位单元格 = matrix[0][0]
        table[0][0] = matrix[0][0];

        // 此步骤是初始化从起点 0, 0 开始，直着向右 或 直着向下的 每一步所需路径和
        //      第一行表格的值，都等于 当前单元格的值 + 上一个单元格的值
        for(int k = 1; k < i; k++) table[0][k] = matrix[0][k] + table[0][k - 1];

        //      第一列表格的值，都等于 当前单元格的值 + 上一行单元格的值
        for(int k = 1; k < j; k++) table[k][0] = matrix[k][0] + table[k - 1][0];


        // 从1，1开始，每次填充的表格 = min(当前单元格 + 上一个单元格的值，当前单元格 + 左边单元格的值) 取最小路径和
        for(int m = 1; m < i; m++){
            for(int n = 1; n < j; n++){
                table[m][n] = Math.min(matrix[m][n] + table[m - 1][n], matrix[m][n] + table[m][n - 1]);
            }
        }
        // 循环结束， 表格最后一个元素即为解
        return table[i-1][j-1];
    }
}

发表于 2022-11-22 14:46:07 回复(0)

Java

624huiguorou

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int rows = matrix.length, columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < rows; i++) dp[i][0] = dp[i-1][0] + matrix[i][0];
        for (int j = 1; j < columns; j++) dp[0][j] = dp[0][j-1] + matrix[0][j];
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[rows-1][columns-1];
    }

    
}

发表于 2022-09-19 16:35:26 回复(0)

Java

超可爱超超

        int n = matrix[0].length;//行数

        int m = matrix.length;//列数

        //填充数据
        int[][] len = new int[m][n];
        //len = matrix;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    len[0][0] = matrix[i][j];
                } else if (i == 0) {
                    len[i][j] = matrix[i][j] + len[i][j - 1];
                } else if (j == 0) {
                    len[i][j] = matrix[i][j] + len[i - 1][j];
                } else {
                    len[i][j] = Math.min(len[i][j - 1], len[i - 1][j]) + matrix[i][j];
                }
            }

        }

        return len[m-1][n-1];

发表于 2022-09-06 10:48:34 回复(0)

Java

程序员大鹏

public int minPathSum (int[][] matrix) {
        // write code here
        
        
        int x = matrix.length;
        int y = matrix[0].length;
        
        
        int[][] cache = new int[x][y];
        
        for(int i = x-1;i>=0;i--) {
            for(int j = y-1;j>=0;j--) {
                if(i == x-1 && j == y-1) {
                    cache[x-1][y-1] = matrix[x-1][y-1];
                } else if(i == x-1) {//最右一排，只算下方路径
                    cache[i][j] = cache[i][j+1] + matrix[i][j];
                } else if(j == y-1) {//最下一排，只算右侧路径
                    cache[i][j] = cache[i+1][j] + matrix[i][j];
                } else {// 需要比较有侧和下方哪个最小
                    int xPath = 0,yPath = 0;
                    cache[i][j] = Math.min(cache[i+1][j] + matrix[i][j],
                                           cache[i][j+1] + matrix[i][j]);
                }
            }
        }
        
        return cache[0][0];
    }

发表于 2022-08-25 00:08:45 回复(0)

Java

yxjing

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int row=matrix.length;
        int col=matrix[0].length;
        int[][] dp=new int[row][col];//表示ij位置到右下的最小路径和
        //初始化
        dp[row-1][col-1]=matrix[row-1][col-1];
        for(int j=col-2;j>=0;j--){
            dp[row-1][j]=dp[row-1][j+1]+matrix[row-1][j];
        }
        for(int i=row-2;i>=0;i--){
            dp[i][col-1]=dp[i+1][col-1]+matrix[i][col-1];
        }
        //转移
        for(int i=row-2;i>=0;i--){
            for(int j=col-2;j>=0;j--){
                dp[i][j]=Math.min(dp[i][j+1],dp[i+1][j])+matrix[i][j];
            }
        }
        //返回
        return dp[0][0];
    }
}

发表于 2022-08-08 15:37:22 回复(0)

Java

牛客5514606号

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int m=matrix.length;
        int n=matrix[0].length;
        int[][] dp=new int[m][n];
        int sum1=0;
        int sum2=0;
        for(int i=0;i<m;i++)
        {
            sum1+=matrix[i][0];
            dp[i][0]=sum1;
        }
        for(int j=0;j<n;j++)
        {
            sum2+=matrix[0][j];
            dp[0][j]=sum2;
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+matrix[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

发表于 2022-07-16 17:38:40 回复(0)

Java

进入人才池

public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = matrix[0][0];
        for ( int i = 1; i < n; i++ ) dp[0][i] = dp[0][i-1] + matrix[0][i];
        for ( int i = 1; i < m; i++ ) dp[i][0] = dp[i-1][0] + matrix[i][0];
        
        for ( int i = 1; i < m; i++ ) {
            for ( int j = 1; j < n; j++ ) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

发表于 2022-06-19 22:06:07 回复(0)

Java

NiKoDad

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        // write code here
        int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (i == 1) {
                    dp[i][j] = dp[i][j - 1] + matrix[i - 1][j - 1];
                } else if (j == 1) {
                    dp[i][j] = dp[i - 1][j] + matrix[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i - 1][j - 1];
                }
            }
        }
        return dp[matrix.length][matrix[0].length];
    }
}

发表于 2022-06-02 15:14:21 回复(0)

Java

毛豆来啦

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = matrix[0][0];
        //处理第一行
        for(int i = 1;i<col;i++){
            dp[0][i] = dp[0][i-1] + matrix[0][i];
        }
        //处理第一列
        for(int i = 1;i<col;i++){
            dp[i][0] = dp[i-1][0] + matrix[i][0];
        }
        //动态计算
        for(int i = 1; i < col;i++){
            for(int j = 1; j < row ; j++){
                dp[j][i] = matrix[j][i] + Math.min(dp[j][i-1],dp[j-1][i]);
            }
        }
        return dp[row-1][col-1];
    }
}

发表于 2022-05-10 14:53:00 回复(0)

Java

精灵鼠201906031611131

和大家的思路是一样的。达到x,y可能是从x-1,y 或者是x,y-1。到达该点的最小路径应该是从上个节点的两个中取较小的值+当前节点的值。首先需要出示化第一行和第一列的最小路径，因为后面的计算依赖第一行和第一列中每个节点的最小路径

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        if(matrix==null)
            return 0;
        int height = matrix.length;
        int width = matrix[0].length;
        
        for(int i = 1; i<height; i++) {
            matrix[i][0] += matrix[i-1][0];
        }
        
        for(int j = 1; j<width ; j++) {
            matrix[0][j] += matrix[0][j-1];
        }
        
        for(int i = 1; i<height; i++) {
            for(int j = 1; j<width; j++) {
                matrix[i][j] += Math.min(matrix[i-1][j], matrix[i][j-1]);
            }
        }
        
        return matrix[height-1][width-1];
    }
}

发表于 2022-04-21 16:09:56 回复(0)

Java

輝长六加1

二维dp

import java.util.*;
public class Solution {
  public int minPathSum (int[][] matrix) {
      if (null == matrix) {
          return 0;
      }

      int m = matrix.length;
      int n = matrix[0].length;

      // 二维dp
      int[][] dp = new int[m + 1][n + 1];
      // 初始化
      for (int[] num : dp) {
          Arrays.fill(num, Integer.MAX_VALUE);
      }
      // 这里方便计算第一个值
      dp[0][1] = dp[1][0] = 0;

      // 遍历矩阵
      for (int i = 1;i <= matrix.length;i++) {
          for (int j = 1;j <= matrix[0].length;j++) {
              // 取左边和上面的较小值再累加
              dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 
                          matrix[i - 1][j - 1];
          }
      }

      return dp[m][n];
  }
}

一维dp

import java.util.*;
public class Solution {
  public int minPathSum (int[][] matrix) {
      if (null == matrix) {
          return 0;
      }

      int m = matrix.length;
      int n = matrix[0].length;

      // 一维dp
      int[] dp = new int[n + 1];
      // 初始化
      Arrays.fill(dp, Integer.MAX_VALUE);
      // 这里方便计算第一个值
      //dp[0] = 0;

      // 遍历矩阵
      for (int i = 1;i <= matrix.length;i++) {
          for (int j = 1;j <= matrix[0].length;j++) {
              if (i == 1 && j == 1) {
                  // 第一个元素特殊处理
                  dp[j] = matrix[0][0];
              } else {
                  // 取左边和上面的较小值再累加
                  dp[j] = Math.min(dp[j], dp[j - 1]) + 
                          matrix[i - 1][j - 1];
              }
          }
      }

      return dp[n];
  }
}

发表于 2022-04-04 11:20:02 回复(0)

Java

江_小_白

import java.util.*;
 
 
public class Solution {
    /**
     *
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int m=matrix.length;
        int n=matrix[0].length;
        for(int i=1;i<m;i++){
            matrix[i][0]+=matrix[i-1][0];
        }
        for(int j=1;j<n;j++){
            matrix[0][j]+=matrix[0][j-1];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                matrix[i][j]+=Math.min(matrix[i-1][j],matrix[i][j-1]);
            }
        }
        return matrix[m-1][n-1];
    }
}

发表于 2022-03-25 20:35:48 回复(0)

Java

只要三星剑姬

public int minPathSum (int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int[][] dp = new int[m][n];
        //
        dp[m-1][n-1]=matrix[m-1][n-1];
        for (int i = m-2; i >=0; i--) {
            dp[i][n - 1] = dp[i+1][n-1]+matrix[i][n - 1];
        }
        for (int i = n-2; i >=0; i--) {
            dp[m - 1][i] =dp[m-1][i+1]+matrix[m - 1][i] ;
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = m-2; j >=0 ; j--) {
                dp[j][i] =matrix[j][i]+Math.min(dp[j+1][i] , dp[j][i + 1]) ;
            }
        }

        return dp[0][0];
    }

发表于 2022-03-16 22:42:11 回复(0)

Java

FARO_Z

方法一：暴解

private int minSum = Integer.MAX_VALUE;
    public int minPathSum (int[][] matrix) {
        dfs(0,0,matrix.length-1,matrix[0].length-1,0,matrix);
        return minSum;
    }

    private void dfs(int r,int c,int rLeft,int cLeft,int sum,int[][] matrix) {
        sum+=matrix[r][c];
        if (rLeft==0 && cLeft==0) {
            minSum = Math.min(sum,minSum);
            return;
        }
        if (rLeft>0) dfs(r+1,c,rLeft-1,cLeft,sum,matrix);
        if (cLeft>0) dfs(r,c+1,rLeft,cLeft-1,sum,matrix);
    }

方法二：暴解优化

private int minSum = Integer.MAX_VALUE;
    public int minPathSum (int[][] matrix) {
        // 记录之前走到当前位置的最小值
        int[][] memo = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < memo.length; i++) {
            for (int j = 0; j < memo[0].length; j++) {
                memo[i][j]=-1;
            }
        }
        dfs(0,0,matrix.length-1,matrix[0].length-1,0,matrix,memo);
        return minSum;
    }

    private void dfs(int r,int c,int rLeft,int cLeft,int sum,int[][] matrix,int[][] memo) {
        sum+=matrix[r][c];
        if (memo[r][c]==-1) {
            memo[r][c]=sum;
        }
        // 大于之前某次的走法，排除以减小递归
        if (sum>memo[r][c]) return;
        if (rLeft==0 && cLeft==0) {
            minSum = Math.min(sum,minSum);
            return;
        }
        if (rLeft>0) dfs(r+1,c,rLeft-1,cLeft,sum,matrix,memo);
        if (cLeft>0) dfs(r,c+1,rLeft,cLeft-1,sum,matrix,memo);
    }

方法三：动态规划

public int minPathSum (int[][] matrix) {
        int R = matrix.length;
        int C = matrix[0].length;
        if (matrix==null || R*C==0) return 0;
        int[][] dp = new int[R][C];
        for (int i = 0; i < C; i++) {
            if (i==0) dp[0][i]=matrix[0][i];
            else dp[0][i]=matrix[0][i]+dp[0][i-1];
        }
        for (int i = 0; i < R; i++) {
            if (i==0) dp[i][0]=matrix[i][0];
            else dp[i][0]=matrix[i][0]+dp[i-1][0];
        }
        for (int i = 1; i < R; i++) {
            for (int j = 1; j < C; j++) {
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + matrix[i][j];
            }
        }
        //for (int i = 0; i < R; i++) {
        //    System.out.println(Arrays.toString(dp[i]));
        //}
        return dp[R-1][C-1];
    }

发表于 2022-03-16 18:17:40 回复(0)

Java

爱学习的小清哥

//暴力搜索，复杂度过高，不通过！
public class Solution {
    ArrayList<Integer> list = new ArrayList<>();
    public int minPathSum (int[][] matrix) {
        // write code here
        int res=Integer.MAX_VALUE;
        recur(matrix,0,0,0);
        for(int i:list){
            res=Math.min(i,res);
        }
        return res;
    }
    public void recur(int[][] matrix, int i, int j,int count){
        if(i<0||j<0||i>=matrix.length||j>matrix[0].length) return;
        if(i==matrix.length-1 && j==matrix[0].length-1) {
            list.add(count+matrix[i][j]);
            return;
        }
        
        if(i<matrix.length-1){
            recur(matrix, i+1,j,count+matrix[i][j]);
        }
        if(j<matrix[0].length-1){
            recur(matrix, i,j+1,count+matrix[i][j]);
        }
    }
}

发表于 2022-03-14 22:35:00 回复(0)

矩阵的最小路径和

输入

输出

输入

输出

备注:

方法一：暴解

方法二：暴解优化

方法三：动态规划

问题信息

热门推荐

通过挑战的用户

相关试题