题目(算法课第八课)
给你一个二维数组,二维数组中的每个数都是正数,要求从左上角走到右下角,每一步只能向右或者向下。沿途经过的数字要累加起来。返回最小的路径和。
举例
如果给定的m如下,那么路径1,3,1,0,6,1,0
就是最小路径和,返回12
1 | 1 3 5 9 |
思路
思路1:递归
每个位置只能向右 或者 向下走,每次走最短的,无后效性。
代码1:
1 | public static int minPath1(int[][] matrix) { |
思路2:动态规划
运用动态规划,我们在递归的时候了解到,(i,j)位置的值依赖它左边或者上边的值,所以我们就先把它依赖的求出来,然后从左上开始向(i,j)求,相当于把递归的过程反过来。申请一个新的二维数组空间,分别求出第一行和第一列的累计和的值,然后再求(i,j)位置的值时就可以根据已经求出的第一行和第一列的累计和来算(把每个i,j位置的路径和都算出来),先找出不被依赖的,再求出依赖的。
步骤
假设矩阵m的大小为M×N,行数为M,列数为N。
1. dp[i][j]
生成大小和m一样的矩阵dp,dp[i][j]的值表示从左上角(即(0,0))位置走到(i ,j)位置的最小路径和。
2. base case
对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]这些值的累加结果。
以题目中的例子
1 | 1 3 5 9 |
来说,dp第一行和第一列的值如下:
1 | 1 4 9 1 8 |
3. “补表”
除第一行和第一列,其他位置(i ,j)都有左边位置(i-1,j)和上边位置(i ,j-1)。从(0,0)到(i ,j)的路径必然经过位置(i-1,j)或位置(i ,j-1)——所以
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]的值。
以题目的例子
1 | 1 3 5 9 |
来说,最终生成的dp矩阵如下:
1 | 1 4 9 18 |
代码2:
1 | public static int minPath2(int[][] m) { |
总的代码
1 | public class MinPath { |
输出:
1 | 12 |