动态规划问题：矩阵的最小路径和

题目：

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。 示例： m n 4 4 1 3 5 9 8 1 3 4 5 0 6 1 8 8 4 0 输出：12

解法一：

更新整个矩阵 第一行和第一列只需要直接求和更新即可 其余部分可以看到 矩阵只能从左边或者上边经过，只需要比较左边和上边的数的大小，取小的即可。

public 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];

解法二

解法一的空间还可以压缩。8 1 3 4 可以只采用一个数组进行滚动更新。 为节省空间可以选择维度较小的数组开始。 迭代过程前几步 1 3 5 9 -> 1 4 9 18 -> 9 3 9 18 ->9 5 9 18

public int minPathSum2(int [][] m){ if (m == null || m.length == 0 || m[0] == null || m[0].length = 0){ return 0; } int more = Math.max(m.length,m[0].length);// 行和列相对小的数 int less = Math.min(m.length, m[0].length);// 行和列相对大的数 boolean colIsMore = more == m[0].length;// 标志列是不是相对大的那个 int[] dp = new int[less]; dp[0] = m[0][0]; for (i = 1;i < less; i++){ dp[i] = dp[i-1] + (colIsMore ? m[0][i] : m[i][0]); } for (i = 1;i < more;i++){ dp[0] = dp[0] + (colIsMore ? m[i][0] : m[0][i]); for (j = 1;j < less;j++){ dp[i] = Math.min(dp[i], dp[i-1]) + (colIsMore ? m[i][j] : m[j][i]); } } return arr[more - 1];

备注 ： 如果题目中需要打印起点到所有点之间的最小路径则不能使用空间压缩的方法。空间压缩后过程中的值会被覆盖，不可回溯。