3
#yyds干货盘点# 面试必刷TOP101：矩阵的最小路径和
source link: https://blog.51cto.com/u_15488507/5723528
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 面试必刷TOP101：矩阵的最小路径和
精选 原创1.简述：
描述
给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
数据范围: ，矩阵中任意值都满足
要求：时间复杂度
例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12，
所选择的最小累加和路径如下图所示：
示例1
[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
示例2
[[1,2,3],[1,2,3]]
2.代码实现：
import java.util.*;
public class Solution {
public int minPathSum (int[][] matrix) {
int n = matrix.length;
//因为n,m均大于等于1
int m = matrix[0].length;
//dp[i][j]表示以当前i，j位置为终点的最短路径长度
int[][] dp = new int[n + 1][m + 1];
dp[0][0] = matrix[0][0];
//处理第一列
for(int i = 1; i < n; i++)
dp[i][0] = matrix[i][0] + dp[i - 1][0];
//处理第一行
for(int j = 1; j < m; j++)
dp[0][j] = matrix[0][j] + dp[0][j - 1];
//其他按照公式来
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
dp[i][j] = matrix[i][j] + (dp[i - 1][j] > dp[i][j - 1] ? dp[i][j - 1] : dp[i - 1][j]);
}
}
return dp[n - 1][m - 1];
}
}
public class Solution {
public int minPathSum (int[][] matrix) {
int n = matrix.length;
//因为n,m均大于等于1
int m = matrix[0].length;
//dp[i][j]表示以当前i，j位置为终点的最短路径长度
int[][] dp = new int[n + 1][m + 1];
dp[0][0] = matrix[0][0];
//处理第一列
for(int i = 1; i < n; i++)
dp[i][0] = matrix[i][0] + dp[i - 1][0];
//处理第一行
for(int j = 1; j < m; j++)
dp[0][j] = matrix[0][j] + dp[0][j - 1];
//其他按照公式来
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
dp[i][j] = matrix[i][j] + (dp[i - 1][j] > dp[i][j - 1] ? dp[i][j - 1] : dp[i - 1][j]);
}
}
return dp[n - 1][m - 1];
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK