# 不同路径
一个机器人位于一个`m x n`网格的左上角（起始点在下图中标记为`Start` ）。  
机器人每次只能向下或者向右移动一步，机器人试图达到网格的右下角（在下图中标记为`Finish`）。  


| Start |  | | | | | |
|---|---|---|---|---|---|---|
| | | | | | | |
| | | | | | | Finish |


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

## 示例

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

```
输入: m = 7, n = 3
输出: 28
```

## 题解

```javascript
/**
 * @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/
```