62. Unique Paths
有一個機器人在 m x n 的網格上。機器人最初位於左上角(即 grid[0][0])。機器人試圖移動到右下角(即 grid[m - 1][n - 1])。機器人每次只能向下或向右移動。
給定兩個整數 m 和 n,返回機器人到達右下角的唯一路徑數。
測試用例生成的答案將小於或等於 2 * 10^9。
範例 1:
輸入:m = 3,n = 7 輸出:28
Python
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# Initialize a 2D array with all elements set to 1
dp = [[1] * n for _ in range(m)]
# Fill the dp array
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]
16.29MB, 28ms
C++
class Solution {
public:
int uniquePaths(int m, int n) {
// Create a 2D array initialized to 1
vector<vector<int>> dp(m, vector<int>(n, 1));
// Fill the dp array
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];
}
};
7.76MB, 0ms
Javascript
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
// Initialize a 2D array with all elements set to 1
const dp = Array.from({ length: m }, () => Array(n).fill(1));
// Fill the dp array
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];
};
48.69MB, 53ms