目录

62_不同路径

lienhui68 收录于技术

2020-07-12 约 711 字预计阅读 2 分钟次阅读

目录

题目

leetcode # 62 不同路径一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例：输入: m = 7, n = 3 输出: 28

分析

dp问题，和青蛙跳台阶类似抽象出状态转换方程，f(m,n)表示到坐标(m,n)的可能数，有两种可能，该坐标位置的上方或者下方进入。所以 f(m,n)=f(m-1,n)+f(m,n-1) 其中f(i,0)或者f(0,j) 等于1，因为走到墙壁只有一条路就是沿着墙壁走到黑。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


public static int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            f[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            f[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = f[i][j - 1] + f[i - 1][j];
            }
        }
        return f[m - 1][n - 1];
    }

优化

同{%post_link 工作/100_计科基础/数据结构与算法/leetcode/最小路径和_64%}，我们也可以使用一维，数组来保存最优解，使得空间复杂度从o(m*n)降到o(min(m,n))

优化后的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public static int uniquePaths(int m, int n) {
        int[] f = new int[n];
        for (int j = 0; j < n; j++) {
            f[j] = 1;
        }
        for (int i = 1; i < m; i++) {
            // f[0] = f[0]; 每一行的最左边最优解都是1， 不用写
            for (int j = 1; j < n; j++) {
                f[j] = f[j - 1] + f[j];
            }
        }
        return f[n - 1];
    }

本题中的压缩空间的方法几乎可以应用到所有的二维动态规划的题目，通过一个数组滚动更新的方式无疑节省了大量的空间。没有优化之前，求某个位置动态规划值的过程是在矩阵中进行两次寻址，程序的常数时间也得到了一定程度的加速，但是空间压缩的方法是有局限性的，如果本题改成打印具有最小路径和的路径，就不能使用空间压缩的方法。