LeetCode62

ゝ一纸荒年。 2022-01-20 08:53 194阅读 0赞

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

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

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

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

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

示例 1:

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

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

思路：转换成了动态规划，以前总以为动态规划只能求最大值或者最小值。多了新套路。

方程是 f(x,y) = f(x,y-1)+f(x-1,y); f(0,j...m) = 1.f(i...n,0) = 1;

**一定要注意特殊条件 即 m = 1,n = 1.return 1;**

class Solution {
    public:
        int uniquePaths(int m, int n) {
            
            int** mn = new int*[n];
            
            for(int ni = 0;ni<n;ni++){
                
                mn[ni] = new int[m];
            }
            if(m==1&&n==1)
                return 1;
            
            for(int i = 1;i<n;i++){
                
                mn[i][0] = 1;
            }
            for(int j = 1;j<m;j++){
                mn[0][j] = 1;
            }
            
            for(int i = 1;i<n;i++){
                
                for(int j = 1;j<m;j++){
    
                
                    mn[i][j] = mn[i][j-1]+mn[i-1][j];
                    
                }
                
            }
            
            return mn[n-1][m-1];
            
        }
    };

![robot_maze.png][]

[robot_maze.png]: /images/20220120/87f30d5612284b7ab7d7344090725d3d.png

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-62. 不同路径

题目来源 [62. 不同路径][62.] 递归 class Solution { public int uniquePat

迈不过友情╰/ 2024年03月26日 17:00/ 0 赞/ 53 阅读

相关 LeetCode 62. 不同路径

题目链接[https://leetcode.cn/problems/unique-paths/][https_leetcode.cn_problems_unique-paths

╰半橙微兮°/ 2024年02月19日 10:06/ 0 赞/ 43 阅读

相关 Leetcode 62. 不同路径

Leetcode 62. 不同路径 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.co

- 日理万妓/ 2023年02月14日 02:55/ 0 赞/ 48 阅读

相关 leetcode62不同路径

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

小鱼儿/ 2022年09月04日 06:41/ 0 赞/ 311 阅读

相关 leetcode 62 不同路径

前言题目：[62. 不同路径][62.] 参考题解：[不同路径-代码随想录][-] -------------------- 提交代码一维的动态规划，类似

「爱情、让人受尽委屈。」/ 2022年08月28日 05:52/ 0 赞/ 178 阅读

相关 leetcode 62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram

逃离我推掉我的手/ 2022年08月21日 04:13/ 0 赞/ 142 阅读

相关 LeetCode62——Unique Paths

LeetCode62——Unique Paths 《组合数学》一道题。由于有直接的方法，就没怎么思考。答案是从m+n中选出m或者n个结果的组合数，虽然结果是一样的，这里为

短命女/ 2022年08月09日 13:39/ 0 赞/ 158 阅读

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

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

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

相关 leetcode:62. 不同路径

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

浅浅的花香味﹌/ 2022年04月05日 13:44/ 0 赞/ 201 阅读

相关 LeetCode62

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

ゝ一纸荒年。/ 2022年01月20日 08:53/ 0 赞/ 195 阅读