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

分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.RecursionAndDynamicPrograming; /** * 矩阵的最小路径和 * * 【题目】 * 给定一个矩阵m从左上角开始每次只能向右或者向下走最后到达右下角的位置路径上所有的数字累加起来就是路径和返回所有 * 的路径中最小的路径和。 * * 【难度】 * 中等 * * 【解答】 * 经典动态规划方法。假设矩阵m的大小为MxN行数为M列数为N。先生成大小和m一样的矩阵dpdp[i][j]的值表示从左上角 * 即(0,0)位置走到(i,j)位置的最小路径和。对m的第一行的所有位置来说即(0,j)(0jN)从(0,0)位置走到(0,j)位置只能 * 向右走所以(0,0)位置到(0,j)位置的路径和就是m[0][0..j]这些值的累加结果。同理对m的第一列的所有位置来说即(i,0) * (0iM)从(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 */