Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LeetCode 62. 不同路径 #70

Open
Chocolate1999 opened this issue Oct 6, 2020 · 0 comments
Open

LeetCode 62. 不同路径 #70

Chocolate1999 opened this issue Oct 6, 2020 · 0 comments
Labels
动态规划 动态规划DP

Comments

@Chocolate1999
Copy link
Owner

仰望星空的人,不应该被嘲笑

题目描述

一个机器人位于一个 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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

机器人只能向右或向下移动一步,那么当前路径数等于左边路径数+上边路径数之和,不过初始化第0行和第0列路径数都为1。

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
    let dp = new Array(m);
    // 初始化 第0行和第0列路径数都为1
    for (let i = 0; i < m; i++) {
        dp[i] = new Array(n);
        dp[i][0] = 1;
    }
    for (let i = 0; i < n; i++) {
        dp[0][i] = 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];
};

最后

文章产出不易,还望各位小伙伴们支持一波!

往期精选:

小狮子前端の笔记仓库

leetcode-javascript:LeetCode 力扣的 JavaScript 解题仓库,前端刷题路线(思维导图)

小伙伴们可以在Issues中提交自己的解题代码,🤝 欢迎Contributing,可打卡刷题,Give a ⭐️ if this project helped you!

访问超逸の博客,方便小伙伴阅读玩耍~

学如逆水行舟,不进则退
@Chocolate1999 Chocolate1999 added the 动态规划 动态规划DP label Oct 6, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
动态规划 动态规划DP
Projects
None yet
Development

No branches or pull requests

1 participant