目录

62_最小路径和

题目

leetcode # 64. 最小路径和 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。

示例:

输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。

分析

dp问题, f(m,n)表示走到坐标(m,n)的最大路径和,v[i][j]表示坐标(i,j)上的数字 因为到达坐标(m,n)只能从上方(m-1,n)或者左边(m,n-1)过来,所以$f(m,n)=max{f(m-1,n), f(m,n-1)}$ ok, 我们得到了状态转移方程式, 现在看下边界情况,f(i,j) 当i=0时,只有一种方案就是从左到右,所以f(0,j)只能等于f(0,j-1)+v[0][j-1], 同理f(i,j) 当j=0时,只有一种方案就是从上到下,所以f(i,0)只能等于f(i-1,0)+v[i][0]; 其中f(0,0)等于v[0][0]; ok, let’s go!

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public static int uniquePaths(int[][] v) {
        int[][] f = new int[v.length][v[0].length];
        f[0][0] = v[0][0];
        // 当j==0
        for (int i = 1; i < v.length; i++) {
            f[i][0] = f[i - 1][0] + v[i][0];
        }
        // 当i==0
        for (int j = 1; j < v[0].length; j++) {
            f[0][j] = f[0][j - 1] + v[0][j];
        }
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                f[i][j] = Math.min(f[i][j - 1], f[i - 1][j]) + v[i][j];
            }
        }
        return f[v.length - 1][v[0].length - 1];
    }

优化

按照上述代码执行,空间复杂度为o(n*m),其实可以优化达到o(min(m,n)) 每一个格子的最优解是min(上,左)+v(自己),当i=0或者j=0时,子函数的最优解是确定的。 也就是上述的f(0,1),f(0,2),f(0,3)最优解都是确定的。f(1,0),f(2,0),f(3,0)也是确定的,如下图 https://gitee.com/lienhui68/picStore/raw/master/null/20200702221750.png 假设m<n也就是行数小于列数, 我们构建数组f[m]=第一行的最优解列表,遍历到第二行我们可以得到(1,0),(1,1)和(1,2)的最优解再赋值到f[m] 数组,如下, https://gitee.com/lienhui68/picStore/raw/master/null/20200702221922.png 依次类推我们只需要一个数组就可以解决。

优化后的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
     * 空间优化后的不同路径(假设列数小于行数)
     *
     * @param v
     * @return
     */
    public static int uniquePaths(int[][] v) {
        int[] f = new int[v[0].length];
        f[0] = v[0][0];
        // 初始化第一行的最优解
        for (int j = 1; j < v[0].length; j++) {
            f[j] = f[j - 1] + v[0][j];
        }
        // 从上往下从左往右处理每一个坐标的最优解
        for (int i = 1; i < v.length; i++) {
            // 当前行最左边的最优解 f[0]已被滚动更新,f[1]和f[2]还是上一行的最优解
            f[0] = f[0] + v[i][0];
            for (int j = 1; j < v[0].length; j++) {
                // 滚动更新当前行的最优解, f[j-1]表示当前位置的左边最优解,f[j]表示当前位置的上方最优解
                f[j] = Math.min(f[j], f[j - 1]) + v[i][j];
            }
        }
        // 更新到最后一行,f数组的最后一个元素就是右下角坐标的最优解也就是最小和
        return f[v[0].length - 1];
    }