0062._Unique_Paths

发表于 分类于 ， ，

62. Unique Paths 不同路径

难度: Medium

刷题内容

原题连接

内容描述

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

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

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

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

说明：m 和 n 的值均不超过 100。

示例 1:

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

示例 2:

1
2
输入: m = 7, n = 3
输出: 28

解题方案

思路 1 排列组合方式

例子中，m=7、n=3，也就是说，可以向右走6步（m-1）和向下走2步（n-2）；
如果用符号→表示向右走，符号↓表示向下走，那么这道题就变成了，(m-1)个→和(n-1)个↓有多少种排列组合方式，也就是最终

1
2
计算公式：(m-1 + n-1)! ÷ （(m-1)! × （n-1）!）

自行实现阶乘计算函数——factorial即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
// 为了提高算法效率，利用cache缓存计算结果
let cache = {
  1: 1
}
var uniquePaths = function(m, n) {
  return factorial(m + n - 2) / factorial(m - 1) / factorial(n - 1)
};

function factorial(num){
  if(num <= 1) {
    return 1;
  } else if (cache[num]) {
    return cache[num]
  }else{
    let value = num * factorial(num-1);
    cache[num] = value;
    return value
  }
}

思路 2 模拟矩阵
- 时间复杂度: O(N)

- 空间复杂度: O(N)

如果用每个格子上的值表示，当前格子到左上角格子的走法数量的话，那么右下角格子的值就是最终结果，样子如下
| | | |
| - | - | - |
| 1 | 1 | 1 |
| 1 | 2 | 3 |
| 1 | 3 | 6 |
| 1 | 4 | 10 |
| 1 | 5 | 15 |
| 1 | 6 | 21 |
| 1 | 7 | 28 |

发现规律，每个格子的值等于左侧格子值 + 上方格子值，所以用双层循环绘制表格，再去最后的值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
  let metrics = [];
  for (let x = 0; x < m; x++) {
    for (let y = 0; y < n; y++) {
      if (!metrics[x]) {
        metrics[x] = []
      }
      if (y === 0 || x === 0) {
        metrics[x][y] = 1
      } else {
        metrics[x][y] = metrics[x][y - 1] + metrics[x - 1][y]
      }
    }
  }
  return metrics[m-1][n-1];
};