【LeetCode】 62. 不同路径动态规划

r囧r小猫 2021-06-10 20:38 316阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

使用一个矩阵来保存路径的条数

1.  如果机器人在第一行或者第一列，可能的路线数字只能为1
2.  机器人不在第一行和第一列的时候，可能从上边过来的，也可能从左边过来的，所以，可能性就是上边格子的路线数 加上 左边格子的路线数  
    也就是： 当前格子路线数 = 上边格子路线数 + 左边格子路线数

### 代码 ###

class Solution { 
        public int uniquePaths(int m, int n) { 
            int[][] dp = new int[m][n];
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    if (i == 0 || j == 0) { 
                        dp[i][j] = 1;
                    } else if (i > 0 || j > 0) { 
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
            }
            return dp[m - 1][n - 1];
        }
    }

[Link 1]: https://leetcode-cn.com/problems/unique-paths/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/1ba7697614b54955bafa9218bbd5c019.png

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-62. 不同路径

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

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

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

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

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

相关 leetcode62不同路径

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

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

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

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

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

相关 leetcode 62 不同路径

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

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

相关 LeetCode 62.Unique Paths (不同路径)

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

青旅半醒/ 2022年05月10日 05:30/ 0 赞/ 140 阅读

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

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

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

相关 leetcode:62. 不同路径

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

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

相关每日一道算法题--leetcode 62-- 不同路径（动态规划）--python

【题目描述】【思路一：数学方法】必定要走m+n-2步，从里面选任意m-1步向右即可，组合问题。 import math class Solution(

太过爱你忘了你带给我的痛/ 2021年09月20日 08:28/ 0 赞/ 223 阅读

相关【LeetCode】 62. 不同路径动态规划

<table> <tbody> <tr> <td><font>题目</font></td> </tr> </tbody> </table>

r囧r小猫/ 2021年06月10日 20:38/ 0 赞/ 317 阅读