问题

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）
问总共有多少条不同的路径？
leetcode-62：不同路径 - 图1
示例 1：
输入：m = 3, n = 7
输出：28

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

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

示例 4：
输入：m = 3, n = 3
输出：6

深度优先搜索

这道题目，刚一看最直观的想法就是用图论里的深搜，来枚举出来有多少种路径

注意题目中说机器人每次只能向下或者向右移动一步，那么其实机器人走过的路径可以抽象为一颗二叉树，而叶子节点就是终点！
640 (1).png
此时问题就可以转化为求二叉树叶子节点的个数，代码如下：

  1. class Solution {
  2.     private int dfs(int i, int j, int m, int n) {
  3.         if (i > m || j > n) 
  4.             return 0; // 越界了
  5.         if (i == m && j == n) 
  6.             return 1; // 找到一种方法，相当于找到了叶子节点
  7.         return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
  8.     }
  10.     public int uniquePaths(int m, int n) {
  11.         return dfs(1, 1, m, n);
  12.     }
  13. }

来分析一下时间复杂度，这个深搜的算法，其实就是要遍历整个二叉树

这颗树的深度其实就是m+n-1（深度按从1开始计算）

那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树（其实没有遍历整个满二叉树，只是近似而已）

所以上面深搜代码的时间复杂度为O(2^(m + n - 1) - 1)，可以看出，这是指数级别的时间复杂度，非常大

动态规划

机器人从(0, 0)位置出发，到(m - 1, n - 1)终点

按照动规五部曲来分析：

  • 确定dp数组（dp table）以及下标的含义

    • dp[i][j]：表示从(0, 0)出发，到(i, j)有dp[i][j]条不同的路径

  • 确定递推公式

    • 想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]
    • dp[i - 1][j] 表示，从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理
    • 那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来

  • dp数组的初始化

    • 如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理
      1. for (int i = 0; i < m; i++) 
      2. dp[i][0] = 1;
      3. for (int j = 0; j < n; j++) 
      4. dp[0][j] = 1;

  • 确定遍历顺序

    • 这里要看一下递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了
    • 这样就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的

leetcode-62：不同路径 - 图3

  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         int[][] dp = new int[m][n];
  4.         for (int i = 0; i < m; i++) 
  5.             dp[i][0] = 1;
  6.         for (int j = 0; j < n; j++) 
  7.             dp[0][j] = 1;
  9.         for (int i = 1; i < m; i++) {
  10.             for (int j = 1; j < n; j++) {
  11.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  12.             }
  13.         }
  14.         return dp[m - 1][n - 1];
  15.     }
  16. }

时间复杂度：leetcode-62：不同路径 - 图4
空间复杂度：leetcode-62：不同路径 - 图5

其实用一个一维数组（也可以理解是滚动数组）就可以了，但是不利于理解，可以优化点空间，建议先理解了二维，在理解一维

  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         int[] dp = new int[n];
  4.         for (int i = 0; i < n; i++) 
  5.             dp[i] = 1;
  6.         for (int j = 1; j < m; j++) {
  7.             for (int i = 1; i < n; i++) {
  8.                 dp[i] += dp[i - 1];
  9.             }
  10.         }
  11.         return dp[n - 1];
  12.     }
  13. }
  • 时间复杂度：leetcode-62：不同路径 - 图6
  • 空间复杂度：leetcode-62：不同路径 - 图7