62.不同路径

LeetCode

动态规划解法

确定状态

最后一步

无论机器人用多少种方式到达右下角，最后的一步只能是向下或者向右

右下角的坐标为

那么它的上一步一定是在 或

子问题

如果有种方式走到 ，有 种方式走到，那么走到的方式为种

为什么可以是种

满足加法需要保证两点:

• 无重复，机器人不坑能从的位置走到的位置，不会有重复路线

• 无遗漏，机器人只能从其他两个位置走到最终位置，在没有其他的方式

所以问题就可以转化为有多少种方式走到或的位置，并求两者之和

子问题缩小了元问题的规模，可以忽略最右边一列，或最下面一列，这也是子问题的作用

状态

最终可以确定状态： f[i][j]为机器人有多少种方式走到右下角(i,j)

转移方程

初始条件和边界情况

• 初始条件： f[0][0]=1机器人只有一种方式到左上角，也就是不动

• 边界条件： 第一行和第一列只有一种走法，一直向右或一直向下,因为第一行没有上面的格子，不能从上面走到下面，第一列没有左边的格子，不能从左边走到右边，所以f[0->i][0]=1 f[0][0->j]=1，其他的格子都可以使用状态转移方程

计算顺序

• f[0][0]=1

• 计算第0行： f[0][0],f[0][1],…,f[0][j-1]

• 计算第1行： f[1][0],f[1][1],…,f[1][j-1]

• 计算第i-1行： f[i-1][0],f[i-1][1],…,f[i-1][j-1]

计算顺序并是不里所当然，或是为了循环方便，如下图所示:

B格子在计算i-1行时刚刚算过，A格子在上面一步计算i-2行时计算过，所以可以计算出f[i-1][j-2]为最终返回结果

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

var uniquePaths = function (m, n) {
    var i, j, arr = [];
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (i === 0 || j === 0) {
                Array.isArray(arr[i]) ? arr[i][j] = 1 : arr[i] = [1]
            } else {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
            }
        }
    }
    return arr[i - 1][j - 1];
};

复杂度分析

• 时间复杂度：

• 空间复杂度：