★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Note: m and n will be at most 100.
Example 1:
Input: m = 3, n = 2Output: 3Explanation:From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:1. Right -> Right -> Down2. Right -> Down -> Right3. Down -> Right -> Right
Example 2:
Input: m = 7, n = 3Output: 28
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2输出: 3解释:从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向右 -> 向下2. 向右 -> 向下 -> 向右3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3输出: 28
8ms
1 class Solution { 2 func uniquePaths(_ m: Int, _ n: Int) -> Int { 3 if m == 0 || n == 0 { 4 return 0 5 } 6 var columns: [Int] = Array(repeating: 1, count: m) 7 for _ in 1.. 8ms
1 class Solution { 2 func uniquePaths(_ m: Int, _ n: Int) -> Int { 3 var pathNums = Array(repeating: Array(repeating:0,count: n),count: m) 4 return _helper(&pathNums, m - 1, n - 1) 5 } 6 private func _helper(_ pathNums: inout [[Int]], _ m: Int, _ n: Int) -> Int { 7 if m < 0 || n < 0 { 8 return 0 9 }10 if m == 0 || n == 0 {11 return 112 }13 14 if pathNums[m][n] != 0 {15 return pathNums[m][n]16 }17 pathNums[m][n] = _helper(&pathNums, m - 1, n) + _helper(&pathNums, m, n - 1)18 19 return pathNums[m][n]20 }21 } 12ms
1 class Solution { 2 func uniquePaths(_ m: Int, _ n: Int) -> Int { 3 if m == 0 || n == 0 { return 0 } 4 var count = Array(repeating: Array(repeating: 0, count: n), count: m) 5 var col = n-1 6 while col >= 0 { 7 var row = m-1 8 while row >= 0 { 9 if row == m-1 && col == n-1 {10 count[row][col] = 111 } else {12 count[row][col] = (col < n-1 ? count[row][col+1] : 0) + (row < m-1 ? count[row+1][col] : 0) 13 }14 row -= 115 }16 col -= 117 }18 return count[0][0]19 }20 } 16ms
1 class Solution { 2 3 func uniquePaths(_ m: Int, _ n: Int) -> Int { 4 guard m > 0 else { 5 return 0 6 } 7 8 var steps = Array(repeating: Array(repeating: 1, count: n), count: m) 9 for row in 1.. 20ms
1 class Solution { 2 func uniquePaths(_ m: Int, _ n: Int) -> Int { 3 if m == 0 || n == 0 { 4 return 0 5 } 6 var map = Array(repeating: Array(repeating:0,count: n),count: m) 7 for i in 1 ..< m { 8 for j in 1 ..< n { 9 var num1 = map[i - 1][j]10 var num2 = map[i][j - 1]11 if i - 1 == 0 || j == 0 {12 num1 = 113 }14 if i == 0 || j - 1 == 0 {15 num2 = 116 }17 map[i][j] = num1 + num218 }19 }20 if m - 1 == 0 || n - 1 == 0 {21 return 122 } else {23 let result = map[m - 1][n - 1]24 return result25 }26 }27 } 24ms
1 class Solution { 2 3 func uniquePaths(_ m: Int, _ n: Int) -> Int { 4 var arrs: [[Int]] = Array(repeating: Array(repeating: 0, count: n), count: m) 5 for i in 0.. 32ms
1 class Solution { 2 func uniquePaths(_ m: Int, _ n: Int) -> Int { 3 guard m > 1 else { 4 return m == 0 ? 0 : 1 5 } 6 guard n > 1 else { 7 return n == 0 ? 0 : 1 8 } 9 10 var path = [Int].init(repeating: 1, count: m+1)11 path[0] = 012 for _ in 2...n {13 for j in 1...m {14 path[j] = path[j] + path[j-1]15 }16 }17 print(path)18 return path[m]19 }20 } 40ms
1 class Solution { 2 func uniquePaths(_ m: Int, _ n: Int) -> Int { 3 let l = max(m,n) 4 let s = min(m,n) 5 if s==1 { 6 return 1 7 } 8 // c l,s 组合 9 var ji1 = 110 var ji2 = 111 for i in 1...s-1 {12 ji1*=i13 ji2*=l+s-i-114 }15 return ji2/ji116 }17 }