行业知识
【代码随想录算法训练营Day39】62.不同路径;63. 不同路径 II
2026-11-22 03:31:09
来源:互联网转载
文章目录
- ❇️Day 39 第九章 动态规划 part02
- ✴️今日任务
- ❇️62.不同路径
- 自己的思路
- 自己的代码
- 随想录思路
- 随想录代码
- ❇️63. 不同路径 II
- 自己的思路
- 自己的代码
- 随���录代码
❇️Day 39 第九章 动态规划 part02
✴️今日任务
今天开始逐渐有 dp的感觉了,题目不多,就两个 不同路径,可以好好研究一下
()- 62.不同路径
- 63.不同路径 II
❇️62.不同路径
- 本题大家掌握动态规划的方法就可以。 数论方法 有点非主流,很难想到。
- 题目链接:https://leetcode.cn/problems/unique-paths/
- 视频讲解:https://www.bilibili.com/video/BV1ve4y1x7Eu
- 文章链接:https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html
自己的思路
- dp数组及下标的含义
定义一个二维数组dp[i][j]表示机器人到第i行第j列的格有dp[i][j]种路径
i的最大值为m,j的最大值为n
()int dp[][] = new int[m + 1][n + 1];
- 递归函数
当前格可以通过上面一格往下或左面一格往右
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
- dp数组初始化
dp[0][], dp[][0]相当于在网格上面和左边分别多增加一行一列
dp[1][1] = 1; dp[0][] = 0; dp[][0] = 0;
- 遍历顺序
先从上到下再从左到右
dp[1][1]->dp[2][1]->···->dp[m][1]->dp[1][2]->dp[2][2]->···
或从左到右在从上到下
dp[1][1]->dp[1][2]->···->dp[1][n]->dp[2][1]->dp[2][2]->···
- 打印dp数组
自己的代码
class Solution { public int uniquePaths(int m, int n) { int dp[][] = new int[m + 1][n + 1]; dp[1][1] = 1; for (int i = 0; i dp[i][0] = 0; } for (int j = 0; j dp[0][j] = 0; } for (int i = 1; i for (int j = 1; j if(i == 1 && j == 1) continue; dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } //System.out.println(Arrays.toString(dp[i])); } return dp[m][n]; }} int[][] dp = new int[m][n]; //初始化 for (int i = 0; i - dp数组及下标的含义