算法刷题Day 48 打家劫舍+打家劫舍II+打家劫舍III

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

Day 48 动态规划

198. 打家劫舍

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];

        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for (int i = 2; i < nums.size(); i++)
        {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp.back();
    }
};

213. 打家劫舍II

分成两段来处理:比如说输入的长度是n(0~n-1),就分成[0, n - 1)和[1, n)两部分

class Solution {
    int robSeg(const vector<int> &nums, int left, int right)
    {
        int len = right - left;
        if (len == 0) return 0;
        if (len == 1) return nums[left];
        vector<int> dp(len, 0);
        dp[0] = nums[left];
        dp[1] = max(nums[left], nums[left + 1]);

        for (int i = 2; i < dp.size(); i++)
        {
            dp[i] = max(dp[i - 2] + nums[left + i], dp[i - 1]);
        }

        return dp.back();
    }

public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        return max(robSeg(nums, 0, len - 1), robSeg(nums, 1, len));
    }
};

337. 打家劫舍III

写一个辅助函数,返回两个状态,抢或者不抢能得到的最大收获。文章来源地址https://www.toymoban.com/news/detail-604166.html

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    vector<int> robTree(TreeNode *root) 
    {
        if (!root) return {0, 0}; // {rob, not rob}
        auto leftRet = robTree(root->left);
        auto rightRet = robTree(root->right);

        int sumRob = root->val + leftRet[1] + rightRet[1];
        // int sumNotRob = leftRet[0] + rightRet[0]; // 不偷不是这样写的
        int sumNotRob = max(leftRet[0], leftRet[1]) + max(rightRet[0], rightRet[1]);

        return {sumRob, sumNotRob};
    }

public:
    int rob(TreeNode* root) {
        auto ret = robTree(root);
        return max(ret[0], ret[1]);
    }
};

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

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

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

相关文章

  • Day 42 算法记录|动态规划 09 (打家劫舍)

    1.dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。 2.dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]); 3.初始化,dp[0] 和 dp[1],dp[0] 一定是 nums[0],dp[1] = max(nums[0], nums[1]); 3.遍历顺序,dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历! 进一步对滚动数组

    2024年02月15日
    浏览(35)
  • 213. 打家劫舍 II

    关于此题 我的往期文章,动规五部曲详解篇 : leetCode 213. 打家劫舍 II 动态规划 房间连成环怎么偷呢?_呵呵哒( ̄▽ ̄)\\\"的博客-CSDN博客 https://heheda.blog.csdn.net/article/details/133409962 213. 打家劫舍 II - 力扣(LeetCode) 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定

    2024年02月06日
    浏览(45)
  • leetcode 213. 打家劫舍 II

             本题是 打家劫舍 的进阶版,房屋之间形成一个环了,也就是第一个房屋和最后一个房屋不能一起偷了。那么能偷的情况分为下列三种: 不考虑偷首房间。 不考虑偷尾房间。 不考虑偷首尾房间。         第三种情况包含于第一和第二种情况了,所以分别为第一种

    2024年02月12日
    浏览(36)
  • 【学会动态规划】打家劫舍 II(12)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:213. 打家劫舍 II - 力扣(Lee

    2024年02月15日
    浏览(41)
  • 每日一题之打家劫舍II

    题目链接 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报

    2024年02月08日
    浏览(43)
  • Java 动态规划 Leetcode 213. 打家劫舍 II

    代码展示:         该题其实是Java 动态规划 面试题 17.16. 按摩师的变种,增加了一个首尾是相邻的条件,而我们解决该题也要用到链接的这道题的思想,可以先去看一下上面这篇博客 此题可以采用动态规划的方法进行解决,根据解决动态规划题目的5大步骤进行逐步分析

    2024年02月13日
    浏览(40)
  • LeetCode213.House-Robber-II<打家劫舍II>

      在版本一中增加了一个条件 那就是首尾相关联。那么只需要进行两次循环即可。 第一次是循环是偷第一家的 那么循环到n-1 截至 并且保存一个cmp 第二次循环是不偷第一家的 循环到n截至。然后比较cmp 与 dp [n] 的最大值即可。  

    2024年02月16日
    浏览(45)
  • 打家劫舍 II问题的动态规划解决方案及C++代码实现

    解决打家劫舍 II问题涉及动态规划,将环形问题转化为两个单排问题。通过状态转移方程和初始化,计算可以偷窃到的最高金额。C++代码实现包括状态显示、状态转移方程、初始化、填表顺序和返回值。

    2024年01月21日
    浏览(51)
  • Golang每日一练(leetDay0075) 打家劫舍II、最短回文串

    目录 213. 打家劫舍 II House Robber ii  🌟🌟 214. 最短回文串 Shortest Palindrome  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的

    2024年02月06日
    浏览(46)
  • 动态规划day09(打家劫舍,树形dp)

    目录 198.打家劫舍 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中遇到的困难 213.打家劫舍II 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中遇到的困难 337.打家劫舍 III(树形dp) 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中

    2024年01月23日
    浏览(94)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包