代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
一个机器人位于一个 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
注意：本题与主站 62 题相同： https://leetcode.cn/problems/unique-paths/
我们定义 $f[i][j]$ 表示从左上角走到 $(i, j)$ 的路径数量，初始时 $f[0][0] = 1$，答案为 $f[m - 1][n - 1]$。
考虑 $f[i][j]$：
因此，我们有如下的状态转移方程：
$$ f[i][j] = \begin{cases} 1 & i = 0, j = 0 \\ f[i - 1][j] + f[i][j - 1] & \text{otherwise} \end{cases} $$
最终的答案即为 $f[m - 1][n - 1]$。
时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是网格的行数和列数。
我们注意到 $f[i][j]$ 仅与 $f[i - 1][j]$ 和 $f[i][j - 1]$ 有关，因此我们优化掉第一维空间，仅保留第二维空间，得到时间复杂度 $O(m \times n)$，空间复杂度 $O(n)$ 的实现。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
f = [[0] * n for _ in range(m)]
f[0][0] = 1
for i in range(m):
for j in range(n):
if i:
f[i][j] += f[i - 1][j]
if j:
f[i][j] += f[i][j - 1]
return f[-1][-1]
class Solution {
public int uniquePaths(int m, int n) {
var f = new int[m][n];
f[0][0] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i > 0) {
f[i][j] += f[i - 1][j];
}
if (j > 0) {
f[i][j] += f[i][j - 1];
}
}
}
return f[m - 1][n - 1];
}
}
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> f(m, vector<int>(n));
f[0][0] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i) {
f[i][j] += f[i - 1][j];
}
if (j) {
f[i][j] += f[i][j - 1];
}
}
}
return f[m - 1][n - 1];
}
};
func uniquePaths(m int, n int) int {
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
f[0][0] = 1
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i > 0 {
f[i][j] += f[i-1][j]
}
if j > 0 {
f[i][j] += f[i][j-1]
}
}
}
return f[m-1][n-1]
}
function uniquePaths(m: number, n: number): number {
const f: number[][] = Array(m)
.fill(0)
.map(() => Array(n).fill(0));
f[0][0] = 1;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (i > 0) {
f[i][j] += f[i - 1][j];
}
if (j > 0) {
f[i][j] += f[i][j - 1];
}
}
}
return f[m - 1][n - 1];
}
impl Solution {
pub fn unique_paths(m: i32, n: i32) -> i32 {
let (m, n) = (m as usize, n as usize);
let mut f = vec![1; n];
for i in 1..m {
for j in 1..n {
f[j] += f[j - 1];
}
}
f[n - 1]
}
}
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function (m, n) {
const f = Array(m)
.fill(0)
.map(() => Array(n).fill(0));
f[0][0] = 1;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (i > 0) {
f[i][j] += f[i - 1][j];
}
if (j > 0) {
f[i][j] += f[i][j - 1];
}
}
}
return f[m - 1][n - 1];
};
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
f = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
f[i][j] = f[i - 1][j] + f[i][j - 1]
return f[-1][-1]
class Solution {
public int uniquePaths(int m, int n) {
var f = new int[m][n];
for (var g : f) {
Arrays.fill(g, 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];
}
}
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> f(m, vector<int>(n, 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];
}
};
func uniquePaths(m int, n int) int {
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
for j := range f[i] {
f[i][j] = 1
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
f[i][j] = f[i-1][j] + f[i][j-1]
}
}
return f[m-1][n-1]
}
function uniquePaths(m: number, n: number): number {
const f: number[][] = Array(m)
.fill(0)
.map(() => Array(n).fill(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];
}
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function (m, n) {
const f = Array(m)
.fill(0)
.map(() => Array(n).fill(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];
};
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
f = [1] * n
for _ in range(1, m):
for j in range(1, n):
f[j] += f[j - 1]
return f[-1]
class Solution {
public int uniquePaths(int m, int n) {
int[] f = new int[n];
Arrays.fill(f, 1);
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
f[j] += f[j - 1];
}
}
return f[n - 1];
}
}
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> f(n, 1);
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
f[j] += f[j - 1];
}
}
return f[n - 1];
}
};
func uniquePaths(m int, n int) int {
f := make([]int, n+1)
for i := range f {
f[i] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
f[j] += f[j-1]
}
}
return f[n-1]
}
function uniquePaths(m: number, n: number): number {
const f: number[] = Array(n).fill(1);
for (let i = 1; i < m; ++i) {
for (let j = 1; j < n; ++j) {
f[j] += f[j - 1];
}
}
return f[n - 1];
}
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function (m, n) {
const f = Array(n).fill(1);
for (let i = 1; i < m; ++i) {
for (let j = 1; j < n; ++j) {
f[j] += f[j - 1];
}
}
return f[n - 1];
};
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。