算法刷题Day 39 不同路径+不同路径II

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

Day 39 动态规划

62. 不同路径

递归(深搜)

使用递归的方法超时(可以过37个case)

class Solution {
    int goPath(int m, int n, int curRow, int curCol)
    {
        if (curRow == m - 1 && curCol == n - 1)
        {
            return 1;
        }

        if (curRow >= m || curCol >= n)
        {
            return 0;
        }

        return goPath(m, n, curRow + 1, curCol) + goPath(m, n, curRow, curCol + 1);
    }

public:
    int uniquePaths(int m, int n) {
        return goPath(m, n, 0, 0);
    }
};

来分析一下时间复杂度,这个深搜的算法,其实就是要遍历整个二叉树。

这棵树的深度其实就是m+n-1(深度按从1开始计算)。

那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树(其实没有遍历整个满二叉树,只是近似而已)

所以上面深搜代码的时间复杂度为O(2^(m + n - 1) - 1),可以看出,这是指数级别的时间复杂度,是非常大的。文章来源地址https://www.toymoban.com/news/detail-660018.html

迭代

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> table(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) table[i][0] = 1;
        for (int i = 0; i < n; i++) table[0][i] = 1;

        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                table[i][j] = table[i - 1][j] + table[i][j - 1];
            }
        }

        return table[m - 1][n - 1];
    }
};

63. 不同路径II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        vector<vector<int>> table(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 0));

        for (int i = 0; i < table.size(); i++)
        {
            if (obstacleGrid[i][0]) break;
            table[i][0] = 1;
        }

        for (int i = 0; i < table[0].size(); i++)
        {
            if (obstacleGrid[0][i]) break;
            table[0][i] = 1;
        }

        for (int i = 1; i < table.size(); i++)
        {
            for (int j = 1; j < table[0].size(); j++)
            {
                if (obstacleGrid[i][j]) continue;
                table[i][j] = table[i - 1][j] + table[i][j - 1];
            }
        }

        return table[table.size() - 1][table[0].size() - 1];
    }
};

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

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

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

相关文章

  • 随想录Day39--动态规划: 62.不同路径 , 63. 不同路径 II

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

    2024年02月03日
    浏览(58)
  • 算法D39 | 动态规划2 | 62.不同路径 63. 不同路径 II

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

    2024年04月10日
    浏览(44)
  • 算法day39|动态规划:不同路径Ⅰ、Ⅱ

    https://leetcode.cn/problems/unique-paths/ 了解下标含义——这里是行列数 理解为什么dfs不能做这道题(超时) https://leetcode.cn/problems/unique-paths-ii/ 初始化时也应该注意限制条件 注意特殊情况的判断

    2024年02月06日
    浏览(48)
  • 代码随想录第39天 | 62.不同路径 、 63. 不同路径 II

    一、前言 参考文献:代码随想录 今天主要的题目是动态规划的路径问题,动态规划五要点; 1、确定dp数组,dp[i]代表什么i代表什么; 2、递推公式; 3、初始化dp数组; 4、遍历顺序; 5、打印dp数组; 二、不同路径 1、思路: 我感觉动态规划,我听的很认真,然后这个题目,

    2024年04月13日
    浏览(41)
  • LeetCode刷题笔记【30】:动态规划专题-2(不同路径、不同路径 II)

    参考前文 参考文章: LeetCode刷题笔记【29】:动态规划专题-1(斐波那契数、爬楼梯、使用最小花费爬楼梯) LeetCode链接:https://leetcode.cn/problems/unique-paths/description/ 动态规划 : 创建m×n的数组, 对应这个地图, 数组 val 表示 有几种方法可以走到这一格 最开始, 第一行和第一列v

    2024年02月09日
    浏览(58)
  • 代码随想录Day33 LeetCode T62不同路径 LeetCode T63 不同路径II

    动规五部曲 1.确定dp数组含义 2.确定递推公式 3.初始化数组 4.确定遍历方式 5.打印dp数组查看分析问题 题目链接:62. 不同路径 - 力扣(LeetCode) 注:n行m列而不是m行n列 1.确定dp数组含义 代表到达此下标有多少条路径 2.确定递推公式 因为只能向右或者向下走,所以到达i,j这个点的

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

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

    2024年03月11日
    浏览(58)
  • 算法随想录第三十九天打卡|62.不同路径 , 63. 不同路径 II

    本题大家掌握动态规划的方法就可以。 数论方法 有点非主流,很难想到。  代码随想录 视频讲解: 动态规划中如何初始化很重要!| LeetCode:62.不同路径_哔哩哔哩_bilibili 总结 把m和n弄反了。 https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.htmlhttps://programmercarl.com/00

    2024年01月20日
    浏览(47)
  • LeetCode算法题解(动态规划)|LeetCoed62. 不同路径、LeetCode63. 不同路径 II

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

    2024年02月05日
    浏览(49)
  • 【Leetcode60天带刷】day27回溯算法——39. 组合总和,40.组合总和II,131.分割回文串

    ​ 39. 组合总和 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ,并以列表形式返回。你可以按  任意顺序  返回这些组合。 candidates  中的  同一个  数字可以  无限制重复

    2024年02月11日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包