62.不同路径

描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例：

输入：m = 3, n = 7
输出：28

代码：

function dp(m, n) {
    // 创建一个二维数组，初始填充1
    const arr = new Array(m);
    for(let i = 0; i < m; i++){
        arr[i] = new Array(n).fill(1);
    }
    // 将一个大任务拆解成小任务
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            const top = arr[i][j - 1];
            const left = arr[i - 1][j];
            const cur = arr[i - 1][j] + arr[i][j - 1];
            arr[i][j] = cur;
        }
    }
    return arr[m - 1][n - 1]
}

分析：

定义 f[i][j] 为到达位置 (i,j) 的不同路径数量。

那么 f[m-1][n-1]f[m−1][n−1] 就是我们最终的答案，而 f[0][0] = 1 是一个显而易见的起始条件。

由于题目限定了我们只能 往下 或者 往右 移动，因此我们按照当前可选方向进行分析：

当前位置只能「往下」移动，即有 f[i][j] = f[i-1][j]

当前位置只能「往右」移动，即有 f[i][j] = f[i][j-1]f[i][j]=f[i][j−1]

当前位置即能「往下」也能「往右」移动，即有 f[i][j] = f[i][j-1] + f[i-1][j]

时间复杂度：O(nm) 空间复杂度：O(nm)

总结

这是一道很简单的动态规划入门题目，相信很多同时都做过。

如果我们真正静下来思考这道题的话，会发现还是有很多有价值的东西可以挖掘的。

1. 我们是如何确定本题可以使用动态规划来解决的？

通常我们要从「有无后效性」进行入手分析。 如果对于某个状态，我们可以只关注状态的值，而不需要关注状态是如何转移过来的话，那么这就是一个无后效性的问题，可以考虑使用 DP 解决。 另外一个更加实在的技巧，我们还可以通过 数据范围 来猜测是不是可以用 DP 来做。 因为 DP 是一个递推的过程，因此如果数据范围是 10^510

如果我们不限制只能 往右 和 往下 移动的话，还能使用 DP 来做吗？