题目

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

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

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

示例 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

提示：1 <= m, n <= 100

题目数据保证答案小于等于 2 * 109

注意：本题与主站 62 题相同：

解题思路分析

1、动态规划；时间复杂度O(n^2)，空间复杂度O(n^2)

func uniquePaths(m int, n int) int {
   if m <= 0 || n <= 0 {
      return 0
   }
   dp := make([][]int, n)
   for i := 0; i < n; i++ {
      dp[i] = make([]int, m)
      dp[i][0] = 1
   }
   for i := 0; i < m; i++ {
      dp[0][i] = 1
   }
   for i := 1; i < n; i++ {
      for j := 1; j < m; j++ {
         dp[i][j] = dp[i-1][j] + dp[i][j-1]
      }
   }
   return dp[n-1][m-1]
}

2、动态规划；时间复杂度O(n^2)，空间复杂度O(n)

func uniquePaths(m int, n int) int {
   if m <= 0 || n <= 0 {
      return 0
   }
   dp := make([]int, n)
   for i := 0; i < n; i++ {
      dp[i] = 1
   }
   for i := 1; i < m; i++ {
      for j := 1; j < n; j++ {
         dp[j] = dp[j] + dp[j-1]
      }
   }
   return dp[n-1]
}

3、数学；时间复杂度O(n)，空间复杂度O(1)

// 求C((m+n-2),(m-1))=> (n+m-2)!/(m-1)!(n-1)!
func uniquePaths(m int, n int) int {
   if m == 1 || n == 1 {
      return 1
   }
   if m > n {
      m, n = n, m
   }
   a := 1
   for i := 1; i <= m-1; i++ {
      a = a * i
   }
   b := 1
   for i := n; i <= m+n-2; i++ {
      b = b * i
   }
   return b / a
}

4、递归；时间复杂度O(n^2)，空间复杂度O(n^2)

var arr [][]int

func uniquePaths(m int, n int) int {
   arr = make([][]int, n+1)
   for i := 0; i <= n; i++ {
      arr[i] = make([]int, m+1)
   }
   return dfs(m, n)
}

func dfs(m, n int) int {
   if m <= 0 || n <= 0 {
      return 0
   }
   if m == 1 || n == 1 {
      return 1
   }
   if arr[n][m] > 0 {
      return arr[n][m]
   }
   arr[n][m] = dfs(m, n-1) + dfs(m-1, n)
   return arr[n][m]
}

总结

Medium题目，题目同leetcode 62.不同路径；类似的题目还有：
leetcode 63.不同路径II；
面试题08.02.迷路的机器人