题解 | #矩阵的最小路径和#

矩阵的最小路径和

http://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb

import java.util.*;

public class Solution { /** * * @param matrix int整型二维数组 the matrix * @return int整型 */ public int minPathSum (int[][] matrix) { // write code here int n = matrix.length;//一维数组的长度 int m = matrix[0].length;//二维数组的长度 int[][] dp = new int[n][m];//创建一个二维dp数组 //初始化二维dp数组dp[0][0] dp[0][0] = matrix[0][0]; //初始化二维dp数组第一列 for(int i=1;i<n;i++){ dp[i][0] = dp[i-1][0] + matrix[i][0]; } //初始化二维dp数组第一行 for(int i=1;i<m;i++){ dp[0][i] = dp[0][i-1] + matrix[0][i]; } //遍历,使用动态规划求解,具有最优子结构, //递推关系式:dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + matrix[i][j]; for(int i=1;i<n;i++){ for(int j=1;j<m;j++){ dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + matrix[i][j]; } }

    return dp[n-1][m-1];
}

}

全部评论

相关推荐

04-30 21:35
已编辑
长安大学 C++
晓沐咕咕咕:评论区没被女朋友好好对待过的计小将可真多。觉得可惜可以理解,毕竟一线大厂sp。但是骂楼主糊涂的大可不必,说什么会被社会毒打更是丢人。女朋友体制内生活有保障,读研女朋友还供着,都准备订婚了人家两情相悦,二线本地以后两口子日子美滋滋,哪轮到你一个一线城市房子都买不起的996清高计小将在这说人家傻😅
点赞 评论 收藏
分享
喜欢飞来飞去的雪碧在刷代码:可以试一试字节
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务