Day35 不同路径

一个机器人位于一个 m * n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

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

示例1：

image

输入：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

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10^9

Java解法

思路：

• 走一步回退一步算另一种，明显可以用回溯来处理。没想到超时了。。。但结果是正确的

  static int num = 0;
  public static int uniquePaths(int m, int n) {
      back(m,n,1,1);
      return num;
  }
  public static void back(int x, int y, int startX, int startY) {
      if (startX==x&&startY==y) {
          num++;
          return;
      }
      //向右
      if (startX<x) {
          startX++;
          back(x, y, startX, startY);
          startX--;
      }
      //向下 是否能
      if (startY<y) {
          startY++;
          back(x, y, startX, startY);
      }
  }
  

• 考虑下其他算法，只能向右向下，就想m与n的不同排列组合（官方解2：组合数学）

  
  image

public static int uniquePaths2(int m, int n) {
    long ans = 1;
    for (int x = n, y = 1; y < m; ++x, ++y) {
        ans = ans * x / y;
    }
    return (int) ans;
}

image

官方解

https://leetcode-cn.com/problems/unique-paths/solution/bu-tong-lu-jing-by-leetcode-solution-hzjf/

1. 动态规划

   还能说什么。。666吧

   public int uniquePaths(int m, int n) {
       int[][] f = new int[m][n];
       for (int i = 0; i < m; ++i) {
           f[i][0] = 1;
       }
       for (int j = 0; j < n; ++j) {
           f[0][j] = 1;
       }
       for (int i = 1; i < m; ++i) {
           for (int j = 1; j < n; ++j) {
               f[i][j] = f[i - 1][j] + f[i][j - 1];
           }
       }
       return f[m - 1][n - 1];
   }
   

   • 时间复杂度：O(mn)
   • 空间复杂度：O(mn)

2. 组合数学

   上述解法

   • 时间复杂度：O(min(m,n))
   • 空间复杂度：O(1)