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

矩阵的最小路径和

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-29 18:07
常州大学 Java
寂静羽翼:兄弟我已经亲身经历了,双非没实习很多大厂还是会给笔试的,可是有的公司笔试做的好也不给面一直卡着,ssob基本看我没实习都拒绝我了,但是每天投满偶尔也能有一两场初创公司的面试,但是薪资基本在五六千
点赞 评论 收藏
分享
程序员牛肉:这一眼假啊,基本上都是骗人的,不然就涉及到职位贪腐了,就像之前华为的OD事件,看你运气好不好了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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