不同路径

一个机器人位于一个m x n网格的左上角(起始点在下图中标记为Start )。
机器人每次只能向下或者向右移动一步,机器人试图达到网格的右下角(在下图中标记为Finish)。

Start
Finish

例如,上图是一个7 x 3的网格。有多少可能的路径?

示例

输入: m = 3, n = 2 输出: 3 解释: 从左上角开始,总共有 3 条路径可以到达右下角。 1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右
输入: m = 7, n = 3 输出: 28

题解

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const table = new Array(m).fill(0).map(() => new Array(n).fill(0));
    for(let i=0; i<m; ++i){
        for(let k=0; k<n; ++k){
            if(i === 0 || k === 0) table[i][k] = 1;
            else table[i][k] = table[i-1][k] + table[i][k-1];
        }
    }
    return table[m-1][n-1];
};

思路

相对比较简单的动态规划问题,对于直接根据题目要求绘制一个表格,注意机器人每次只能向下或者向右移动一步,对于题目给出的7 x 3的网格的示例,绘制下面的表格。

1 1 1 1 1 1 1
1 2 3 4 5 6 7
1 3 6 10 15 21 28

根据上面的表格填数据,不难发现其中的规律,最终的终点值无非就是该点的上节点以及左节相加得到的值,也就是说可以通过一个二维数组来搞定,推出动态规划方程式dp[i][j] = dp[i-1][j] + dp[i][j-1],最后将这个数组的最后一个值返回即可。首先初始化数组,直接使用构造函数生成一个m * n的数组并将其填充为0,外层数组填充0的原因是map会跳过empty数组空位,在外层数组填充任何值都可以,会使用map回调函数的返回值覆盖,之后定义循环,在循环中如果某个下标是0的话将其填充为1否则就将该点上节点与左节点的值相加,这样就构造出了上述的表格,之后返回表格的最后一个值即可。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

https://leetcode-cn.com/problems/unique-paths/