力扣00062.不同路径

发表于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 8 分钟
不同路径、数学、动态规划、组合数学、中等

题目描述

一个机器人位于一个 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 * 10^9$

解决方法

C++

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

结果

执行用时 : 0 ms, 击败 100.00% 使用 C++ 的用户

内存消耗 : 7.57 MB, 击败 12.32% 使用 C++ 的用户

Java

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

结果

执行用时 : 0 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 39.46 MB, 击败 21.94% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

结果

执行用时 : 18 ms, 击败 44.36% 使用 Python 的用户

内存消耗 : 11.58 MB, 击败 67.39% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

结果

执行用时 : 32 ms, 击败 92.96% 使用 Python3 的用户

内存消耗 : 16.52 MB, 击败 32.54% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int uniquePaths(int m, int n) {
    int** dp = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; ++i) {
        dp[i] = (int*)malloc(n * sizeof(int));
    }
    for (int i = 0; i < m; ++i) {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n; ++j) {
        dp[0][j] = 1;
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    int result = dp[m-1][n-1];
    for (int i = 0; i < m; ++i) {
        free(dp[i]);
    }
    free(dp);
    return result;
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 C 的用户

内存消耗 : 5.87 MB, 击败 62.56% 使用 C 的用户

C#

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

结果

执行用时 : 15 ms, 击败 95.75% 使用 C# 的用户

内存消耗 : 26.63 MB, 击败 33.02% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const dp = Array.from(Array(m), () => Array(n).fill(0));
    for (let i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (let j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
};

结果

执行用时 : 61 ms, 击败 50.77% 使用 JavaScript 的用户

内存消耗 : 49.11 MB, 击败 30.53% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function uniquePaths(m: number, n: number): number {
    const dp: number[][] = Array.from(Array(m), () => Array(n).fill(0));
    for (let i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (let j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

结果

执行用时 : 67 ms, 击败 43.20% 使用 TypeScript 的用户

内存消耗 : 51.82 MB, 击败 22.00% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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++) {
            $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];
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 PHP 的用户

内存消耗 : 20.29 MB, 击败 9.09% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
        for i in 0..<m {
            dp[i][0] = 1
        }
        for j in 0..<n {
            dp[0][j] = 1
        }
        for i in 1..<m {
            for j in 1..<n {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
        return dp[m - 1][n - 1]
    }
}

结果

执行用时 : 2 ms, 击败 55.56% 使用 Swift 的用户

内存消耗 : 15.24 MB, 击败 6.17% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    fun uniquePaths(m: Int, n: Int): Int {
        val dp = Array(m) { IntArray(n) { 0 } }
        for (i in 0 until m) {
            dp[i][0] = 1
        }
        for (j in 0 until n) {
            dp[0][j] = 1
        }
        for (i in 1 until m) {
            for (j in 1 until n) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
        return dp[m - 1][n - 1]
    }
}

结果

执行用时 : 140 ms, 击败 27.59% 使用 Kotlin 的用户

内存消耗 : 32.59 MB, 击败 34.48% 使用 Kotlin 的用户

Dart

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

结果

执行用时 : 286 ms, 击败 100.00% 使用 Dart 的用户

内存消耗 : 146.46 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        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]
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 1.95 MB, 击败 26.78% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# @param {Integer} m
# @param {Integer} n
# @return {Integer}
def unique_paths(m, n)
  dp = Array.new(m) { Array.new(n, 0) }
  (0...m).each { |i| dp[i][0] = 1 }
  (0...n).each { |j| dp[0][j] = 1 }
  (1...m).each do |i|
    (1...n).each do |j|
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    end
  end
  dp[m - 1][n - 1]
end

结果

执行用时 : 69 ms, 击败 -% 使用 Ruby 的用户

内存消耗 : 206.30 MB, 击败 -% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
object Solution {
  def uniquePaths(m: Int, n: Int): Int = {
    val dp = Array.ofDim[Int](m, n)
    for (i <- 0 until m) {
      dp(i)(0) = 1
    }
    for (j <- 0 until n) {
      dp(0)(j) = 1
    }
    for (i <- 1 until m) {
      for (j <- 1 until n) {
        dp(i)(j) = dp(i - 1)(j) + dp(i)(j - 1)
      }
    }
    dp(m - 1)(n - 1)
  }
}

结果

执行用时 : 398 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 51.44 MB, 击败 33.33% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let mut dp = vec![vec![0; n as usize]; m as usize];
        for i in 0..m as usize {
            dp[i][0] = 1;
        }
        for j in 0..n as usize {
            dp[0][j] = 1;
        }
        for i in 1..m as usize {
            for j in 1..n as usize {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        dp[(m - 1) as usize][(n - 1) as usize]
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 1.98 MB, 击败 79.41% 使用 Rust 的用户

Racket

1
2
3
4
5
6
7
8
9
10
11
12
(define/contract (unique-paths m n)
  (-> exact-integer? exact-integer? exact-integer?)
  (let ((dp (make-vector m (make-vector n 0))))
    (for ([i (in-range m)])
      (vector-set! (vector-ref dp i) 0 1))
    (for ([j (in-range n)])
      (vector-set! (vector-ref dp 0) j 1))
    (for ([i (in-range 1 m)])
      (for ([j (in-range 1 n)])
        (vector-set! (vector-ref dp i) j (+ (vector-ref (vector-ref dp (sub1 i)) j)
                                           (vector-ref (vector-ref dp i) (sub1 j))))))
    (vector-ref (vector-ref dp (sub1 m)) (sub1 n))))

结果

执行用时 : 174 ms, 击败 100.00% 使用 Racket 的用户

内存消耗 : 97.84 MB, 击败 100.00% 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户