leetcode每日一题:62. 不同路径

这篇具有很好参考价值的文章主要介绍了leetcode每日一题:62. 不同路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

系列:动态规划
语言:java
难度:中等
题目来源:Leetcode62. 不同路径
开启动态规划章节了!!欢迎您在留言和我一起完成每日打卡,以后每天8点半前发布每日一题。

原题链接:Leetcode62. 不同路径

题目

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?

示例 1:

leetcode每日一题:62. 不同路径

示例 2:

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

示例 3:

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

示例 4:

输入:m = 3, n = 3
输出:6

约束条件:

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

思路:

分析:动规五部曲。
1.确定dp[i][j]含义:一个二维数组,表示到达i,j这个位置的路径有多少种
2.确定递推公式:因为每次只能向下和向右,所以第dp[i][j]的位置只能由dp[i-1][j](向下的路径方法)和dp[i][j-1](向右的路径方法)合起来组成,dp[i][j] = dp[i-1][j]+dp[i][j-1];
3.初始化dp数组。对于dp[i][0]和dp[0][i]只有一种情况,表示向右和向下只有一种方式。所以规定他们都为1;
4.确定遍历顺序。 因为第i,j位置处的数只能有上面和左面的数推出,所以需要从左到右进行遍历,即一行一行从左到右进行遍历。

代码实现:

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

感谢您的阅读,希望对您有所帮助。关注我,完成每日算法自律打卡,什么时候开始都不晚!!文章来源地址https://www.toymoban.com/news/detail-421478.html

到了这里,关于leetcode每日一题:62. 不同路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【力扣】62. 不同路径 <动态规划>

    一个机器人位于一个 m m m x n n n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径? 示例 1: 输入:m = 3, n = 7 输出:28 示例 2: 输入:m

    2024年02月10日
    浏览(41)
  • 算法训练Day39:62.不同路径 63. 不同路径 II 动态规划

    Category Difficulty Likes Dislikes ContestSlug ProblemIndex Score algorithms Medium (67.70%) 1746 0 - - 0 Tags Companies 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

    2023年04月25日
    浏览(45)
  • 算法D39 | 动态规划2 | 62.不同路径 63. 不同路径 II

    今天开始逐渐有 dp的感觉了,题目不多,就两个 不同路径,可以好好研究一下 62.不同路径  本题大家掌握动态规划的方法就可以。 数论方法 有点非主流,很难想到。  代码随想录 视频讲解: 动态规划中如何初始化很重要!| LeetCode:62.不同路径_哔哩哔哩_bilibili 这个题看

    2024年04月10日
    浏览(44)
  • 随想录Day39--动态规划: 62.不同路径 , 63. 不同路径 II

    今天的路劲问题,思想和昨天的爬楼梯一样,主要还是找到你这个位置是怎么来的,到达dp[i][j]的方法由到达dp[i - 1][j]的方法再加上到达dp[i][j - 1]的方法和。在初始化时,当i=0或者j=0时,到达他们的只有一条路劲,就是直走,所以对它进行初始化。 63. 不同路径 II 加了一个障

    2024年02月03日
    浏览(59)
  • 力扣:62. 不同路径(动态规划,附python二维数组的定义)

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示例 1: 输入:m = 3, n = 7 输出:28 示例 2: 输入:m = 3, n

    2024年02月03日
    浏览(43)
  • 我在代码随想录|写代码Day33 | 动态规划| 路径问题| 62.不同路径,63. 不同路径 II,343. 整数拆分

    🔥博客介绍`: 27dCnc 🎥系列专栏: 数据结构与算法 算法入门 C++项目 🎥 当前专栏: 算法入门 专题 : 数据结构帮助小白快速入门算法 👍👍👍👍👍👍👍👍👍👍👍👍 ☆*: .。. o(≧▽≦)o .。.:*☆ ❤️感谢大家点赞👍收藏⭐评论✍️ 今日学习打卡 代码随想录 - 动态规划

    2024年03月11日
    浏览(62)
  • 2023-08-04 LeetCode每日一题(不同路径 III)

    点击跳转到题目位置 在二维网格 grid 上,有 4 种类型的方格: 1 表示起始方格。且只有一个起始方格。 2 表示结束方格,且只有一个结束方格。 0 表示我们可以走过的空方格。 -1 表示我们无法跨越的障碍。 返回在四个方向(上、下、左、右)上行走时,从起始方格到结束方

    2024年02月14日
    浏览(41)
  • 算法刷刷刷|动态规划篇|509.斐波那契数| 70.爬楼梯| 746.使用最小花费爬楼梯| 62.不同路径| 63不同路径2| 343.正数拆分 | 96.不同的二叉搜索树

    509. 斐波那契数 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n 1 给定 n ,请计算 F(n) 。 70.爬楼梯 746.使用最小花费爬楼梯 给你一个整数

    2023年04月23日
    浏览(56)
  • ( 动态规划) 1035. 不相交的线 ——【Leetcode每日一题】

    难度:中等 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足: nums1[i] == nums2[j] 且绘制的直线不与任何其他连线(非水平线)相交。 请注意,连线即使在端点也不能相交

    2024年02月05日
    浏览(43)
  • ( 动态规划) 516. 最长回文子序列 ——【Leetcode每日一题】

    难度:中等 给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s = “bbbab” 输出:4 解释:一个可能的最长回文子序列为 “bbbb” 。 示例

    2024年02月06日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包