【中等】矩阵的最小路径和－Java：经典动态规划方法

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package live.every.day.ProgrammingDesign.CodingInterviewGuide.RecursionAndDynamicPrograming; /** * 矩阵的最小路径和 * * 【题目】 * 给定一个矩阵m，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有 * 的路径中最小的路径和。 * * 【难度】 * 中等 * * 【解答】 * 经典动态规划方法。假设矩阵m的大小为MxN，行数为M，列数为N。先生成大小和m一样的矩阵dp，dp[i][j]的值表示从左上角 * 即(0,0)位置走到(i,j)位置的最小路径和。对m的第一行的所有位置来说，即(0,j)(0<=j<N)，从(0,0)位置走到(0,j)位置只能 * 向右走，所以(0,0)位置到(0,j)位置的路径和就是m[0][0..j]这些值的累加结果。同理，对m的第一列的所有位置来说，即(i,0) * (0<=i<M)，从(0,0)位置走到(i,0)位置只能向下走，所以(0,0)位置到(i,0)位置的路径和就是m[0..i][0]这些值的累加结果。 * 除第一行和第一列的其他位置(i,j)外，都有左边位置(i-1,j)和上边位置(i,j-1)。从(0,0)到(i,j)的路径必然经过位置(i-1,j) * 或位置(i,j-1)，所以，dp[i][j]=min{dp[i-1][j],dp[i][j-1]}+m[i][j]，含义是比较从(0,0)位置开始，经过(i-1,j) * 位置最终到达(i,j)的最小路径和经过(i,j-1)位置最终到达(i,j)的最小路径之间，哪条路径的路径和更小。那么更小的路径和就是 * dp[i][j]的值。 * 除第一行和第一列之外，每一个位置都考虑从左边到达自己的路径和更小还是从上边达到自己的路径更小。最右下角的值就是整个问题 * 的答案。具体过程请参看如下代码中的minPathSum1方法。 * 矩阵中一共有MxN个位置，每个位置都计算一次从(0,0)位置到达自己的最小路径和，计算的时候只是比较上边位置的最小路径和与左 * 边位置的最小路径和哪个更小，所以时间复杂度为O(MxN)，dp矩阵的大小为MxN，所以额外空间复杂度为O(MxN)。 * * @author Created by LiveEveryDay */ public class MatrixMinPathSum1 { public static int minPathSum1(int[][] m) { if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) { return 0; } int row = m.length; int col = m[0].length; int[][] dp = new int[row][col]; dp[0][0] = m[0][0]; for (int i = 1; i < row; i++) { dp[i][0] = dp[i - 1][0] + m[i][0]; } for (int j = 1; j < col; j++) { dp[0][j] = dp[0][j - 1] + m[0][j]; } for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j]; } } return dp[row - 1][col - 1]; } public static void main(String[] args) { int[][] m = {{1, 3, 5, 9}, {8, 1, 3, 4}, {5, 0, 6, 1}, {8, 8, 4, 0}}; System.out.printf("The min path sum is: %d", minPathSum1(m)); } } // ------ Output ------ /* The min path sum is: 12 */