小工具知识网

当前位置: 首页 > 行业知识 > 【代码随想录算法训练营Day39】62.不同路径;63. 不同路径 II

行业知识

【代码随想录算法训练营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

              自己的思路

              1. dp数组及下标的含义

                定义一个二维数组dp[i][j]表示机器人到第i行第j列的格有dp[i][j]种路径

                i的最大值为m,j的最大值为n

                ()

                int dp[][] = new int[m + 1][n + 1];

              2. 递归函数

                当前格可以通过上面一格往下或左面一格往右

                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

              3. dp数组初始化

                dp[0][], dp[][0]相当于在网格上面和左边分别多增加一行一列

                dp[1][1] = 1; dp[0][] = 0; dp[][0] = 0;

              4. 遍历顺序

                先从上到下再从左到右

                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]->···

              5. 打印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 

上一篇:织梦手机站点优化秘籍,301重定向教程助你轻松提升网站效率!

下一篇:小红书下载攻略,简易步骤,轻松掌握应用下载!