【Day 58 】2024-06-04 - 62. 不同路径

[azl397985856]

62. 不同路径

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/unique-paths/

前置知识

暂无

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

 

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:

输入: m = 7, n = 3
输出: 28
 

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9

[Martina001]

时间复杂度和空间复杂度均为Omn 经典动归题，优化空间后:

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]; } }

[lxy1108]

思路

动态规划 dp[i][j] = dp[i-1][j]+dp[i][j-1]

需要考虑边界情况，且可使用滚动数组优化空间

python3代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1]*n
        for i in range(m):
            tmp = [1]*n
            for j in range(n):
                if not (i==0 and j==0):
                    tmp[j]=(tmp[j-1] if j>0 else 0)+(dp[j] if i>0 else 0)
            dp = tmp
        return dp[-1]

复杂度分析

时间复杂度o(mn) 空间复杂度o(n)

[xy147]

js代码

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];
};

复杂度分析

时间复杂度：O(mn) 空间复杂度：O(mn)

[hillsonziqiu]

动态规划，每个位置决定了向下或向右两个方向。故f[i][j] = f[i -1] + f[j - 1];来决定。

代码

/*
 * @lc app=leetcode.cn id=62 lang=javascript
 *
 * [62] 不同路径
 */

// @lc code=start
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  let dp = new Array(m).fill(1);

  for (let i = 1; i < n; i++) {
    for (let j = 1; j < m; j++) {
      dp[j] += dp[j - 1];
    }
  }

  return dp[m - 1];
};
// @lc code=end

复杂度分析

• 时间复杂度：O(m*n);
• 空间复杂度：O(m*n);

[Hermione666]

class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[1]n] + [[1]+[0] (n-1) for _ in range(m-1)]

print(dp)

    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[-1][-1]