62. 不同路径
一个机器人位于一个 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 <= 1002 * 109原站题解
java 解法, 执行用时: 0 ms, 内存消耗: 38.2 MB, 提交时间: 2023-10-07 11:41:31
class Solution {
public int uniquePaths(int m, int n) {
int[] f = new int[n];
for (int i = 0; i < n; ++i) {
f[i] = 1;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
f[j] += f[j - 1];
}
}
return f[n - 1];
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 15.7 MB, 提交时间: 2023-10-07 11:41:16
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
f = [1] * n
for i in range(1, m):
for j in range(1, n):
f[j] += f[j - 1]
return f[n - 1]
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-10-07 11:40:59
func uniquePaths(m, n int) int {
dp := make([]int, n)
for i := range dp {
dp[i] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[j] += dp[j-1]
}
}
return dp[n-1]
}
javascript 解法, 执行用时: 64 ms, 内存消耗: 41 MB, 提交时间: 2023-10-07 11:40:35
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
for (let i = 0; i < m; i++) {
f[i][0] = 1;
}
for (let j = 0; j < n; j++) {
f[0][j] = 1;
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
};
java 解法, 执行用时: 0 ms, 内存消耗: 38.1 MB, 提交时间: 2023-10-07 11:40:18
class Solution {
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];
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-10-07 11:40:03
func uniquePaths(m, n int) int {
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
dp[i][0] = 1
}
for j := 0; j < n; j++ {
dp[0][j] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[m-1][n-1]
}
python3 解法, 执行用时: 48 ms, 内存消耗: 15.9 MB, 提交时间: 2023-10-07 11:39:31
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0 for i in range(n)] for j in range(m)]
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
python3 解法, 执行用时: 36 ms, 内存消耗: 14.8 MB, 提交时间: 2022-07-18 10:33:36
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
return math.comb(m+n-2, m-1)
php 解法, 执行用时: 4 ms, 内存消耗: 15.2 MB, 提交时间: 2021-07-30 15:46:53
class Solution {
/**
* @param Integer $m
* @param Integer $n
* @return Integer
*/
function uniquePaths($m, $n) {
$dp = array_fill(0, $m, array_fill(0, $n, 0));
for ( $i = 0; $i < $m; $i++ ) {
for ( $j = 0; $j < $n; $j++ ) {
if ( $i == 0 || $j == 0 ) {
$dp[$i][$j] = 1;
} else {
$dp[$i][$j] = $dp[$i-1][$j] + $dp[$i][$j-1];
}
}
}
return $dp[$m-1][$n-1];
}
}