不同路径-DP

青旅半醒 2023-05-31 03:23 5阅读 0赞

# 不同路径 #

> [https://leetcode-cn.com/problems/unique-paths][https_leetcode-cn.com_problems_unique-paths]

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

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

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

![在这里插入图片描述][20191022195411993.png]

说明：m 和 n 的值均不超过 100。

示例 1:

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

示例 2:

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

## 解析 ##

*  无论，m还是n如果是1，那么路径都只有一条
 *  任意一个点，一定是来自于他的上面或者是左边。那么，到他的总路径数量为左边和上面的路径数量加起来。

## 代码 ##

class Solution { 
    public:
        int uniquePaths(int m, int n) { 
            int map[105][105];
            map[1][1] = 1;
            map[1][2] = 1;
            map[2][1] = 1;
            for (int i = 1; i <= m; ++i) { 
                for (int j = 1; j <= n; ++j) { 
                    if (i == 1 || j == 1)
                        map[i][j] = 1;
                    else 
                        map[i][j] = map[i][j-1] + map[i-1][j];
                }
            }
            return map[m][n];
        }
    };

[https_leetcode-cn.com_problems_unique-paths]: https://leetcode-cn.com/problems/unique-paths
[20191022195411993.png]: /images/20230531/290cd916b15145479b14211e0cd5e09a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关 62. 不同路径

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为...

偏执的太偏执、/ 2024年05月24日 01:33/ 0 赞/ 88 阅读

相关 62：不同路径

推吧，我没想到其他方法 class Solution: def uniquePaths(self, m: int, n: int) -> int...

刺骨的言语ヽ痛彻心扉/ 2024年04月19日 09:53/ 0 赞/ 82 阅读

相关 62. 不同路径

62. 不同路径一个机器人位于一个 m ∗ n m \ n m∗n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。

男娘i/ 2024年03月26日 16:47/ 0 赞/ 64 阅读

相关 62.不同路径

62.不同路径题干描述解题思路 1. 深搜 2. 动态规划 2.1 确定dp数组（dp table）以及下标

小灰灰/ 2023年10月16日 16:01/ 0 赞/ 38 阅读

相关不同路径-DP

不同路径 > [https://leetcode-cn.com/problems/unique-paths][https_leetcode-cn.com_problems

青旅半醒/ 2023年05月31日 03:23/ 0 赞/ 6 阅读

相关 leetcode.62.不同路径——动态规划必刷题dp

文章目录 leetcode.62.不同路径动态规划必刷题 leetcode.62.不同路径 [不同路径][Link 1] ![在这里插入图片描述]

阳光穿透心脏的1/2处/ 2022年12月27日 08:44/ 0 赞/ 144 阅读

相关 62. 不同路径

> 一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。 > > 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图

偏执的太偏执、/ 2022年10月10日 01:41/ 0 赞/ 204 阅读

相关 Leetcode 62. 不同路径（简单DP）

题目重述一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在

柔情只为你懂/ 2022年09月03日 13:14/ 0 赞/ 189 阅读

相关 LeetCode-63 不同路径 II（dp）

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi

Love The Way You Lie/ 2022年04月24日 02:38/ 0 赞/ 260 阅读

相关 LeetCode-62 不同路径（dp）

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi

Love The Way You Lie/ 2022年04月24日 02:36/ 0 赞/ 210 阅读