【Day52】代码随想录之动态规划_打家劫舍

这篇具有很好参考价值的文章主要介绍了【Day52】代码随想录之动态规划_打家劫舍。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划理论基础

动规五部曲:
  1. 确定dp数组 下标及dp[i] 的含义。
  2. 递推公式:比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。
  3. 初始化dp数组。
  4. 确定遍历顺序:从前到后or其他。
  5. 打印。
出现结果不正确:
  1. 打印dp日志和自己想的一样:递推公式、初始化或者遍历顺序出错。
  2. 打印dp日志和自己想的不一样:代码实现细节出现问题。

1. 打家劫舍Ⅲ

参考文档:代码随想录

分析:
树的递归三部曲 结合 动规五部曲:

  1. 函数的参数和返回值:返回某个节点偷与不偷得到的金额,所以返回值确定是一个长度为2的数组vector<int>。dp数组为vector<int>的长度为2的数组,dp[0]表示当前节点不偷得到的金额,dp[1]表示当前节点偷得到的金额。
  2. 终止条件:遇到空节点,返回{0, 0}。
  3. 单层递归的逻辑:判断当前节点到底是偷还是不偷取决于孩子节点不偷+根节点偷 或 根节点不偷+孩子节点偷 得到的最大值,所以用后序遍历,也确定了递推公式。
//计算 节点偷与不偷 得到的金额
vector<int> calRob(TreeNode* cur){
	...
	//左孩子 偷和不偷 的金额
	vector<int> left = calRob(cur->left);
	//有孩子 偷和不偷 的金额
	vector<int> right = calRob(cur->right);
	//递推公式
	//偷
	int sum1 = cur->val + left[0] + right[0];
	//不偷
	int sum2 = max(left[0], left[1]) + max(right[0], right[1]);
	//返回当前节点偷与不偷得到的金额
	return {sum2, sum1};
}

代码:文章来源地址https://www.toymoban.com/news/detail-836848.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 {
public:
    int rob(TreeNode* root) {
        //树形dp:考虑 树的遍历顺序 和 处理逻辑
        //后序遍历(❓)左右孩子是否偷对当前节点是否偷是有影响的
        //dp[i]表示这个这个节点偷和不偷的金币值(❓)
        vector<int> res = calRob(root);
        return max(res[0], res[1]);   
    }

    vector<int> calRob(TreeNode* cur){
        if(cur == NULL) return {0,0};

        if(cur->left == NULL && cur->right == NULL) return {0, cur->val};

        vector<int> left = calRob(cur->left);
        vector<int> right = calRob(cur->right);
        //偷
        int sum1 = cur->val + left[0] + right[0];
        //不偷
        int sum2 = max(left[0], left[1]) + max(right[0], right[1]);

        return {sum2, sum1};
    }
};

2. 打家劫舍Ⅱ

参考文档:代码随想录

分析:
房屋之间成环了,相邻两间房子都偷会使警报器响,所以首偷了尾就绝不能偷,首不偷尾可以偷。回顾打家劫舍Ⅰ,dp[i]的含义是考虑[0, i]房子可以偷窃的最大金额,dp[i] = max(dp[i-1], dp[i-2]+nums[i]),根据递推公式,在决定第i间房子可以偷窃的最大金额是受到i-1和i-2的影响的,再往前推i-1受到i-2和i-3的影响,递推下去dp[i]是受到[0-i-1]之前的房子的影响,有可能这些房子会偷,有可能不偷,但是是影响dp[i]的数值的。所以为了避免首对尾的影响,不将首和尾的房间房子一起。
确定动态规划的区间是 [0, nums.size()-2] 和 [1, nums.size()-1] ,返回两个区间得到的最大值。
接下来讨论dp五部曲:

  1. dp[i]含义:考虑[0, i]的房子可以偷窃的最大金额。
  2. 递推公式:dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
  3. 初始化:dp[0] = nums[0], dp[1] = max(dp[0], dp[1]);
  4. 遍历顺序:从前到后更新。

代码:

class Solution {
public:
	//计算从 begin到end 闭区间偷的金额最大值
    int calRob(vector<int>& nums, int begin, int end){
        vector<int> dp(nums.size(), 0);
        
        dp[begin] = nums[begin];
        dp[begin+1] = max(nums[begin+1], nums[begin]);

        for(int i = begin+2; i <= end; i++){
            dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
        }
        
        return dp[end];
    }
    
    int rob(vector<int>& nums) {
        //房屋围成了一个圈,所以递推公式改变,需要标记第一个位置
        //dp[i] = max(dp[i-1], dp[i-2]+nums[i])

        if(nums.size()==1) return nums[0];
        if(nums.size() == 0) return 0;
        if(nums.size() == 2) return max(nums[0], nums[1]);
        
        int sum1 = calRob(nums, 0, nums.size()-2);
        int sum2= calRob(nums, 1, nums.size()-1);

        if(sum1 > sum2) return sum1;
        return sum2;
    }
};

3. 打家劫舍Ⅰ

参考文档:代码随想录

分析:

dp五部曲:

  1. dp[i]含义:考虑[0, i]的房子可以偷窃的最大金额。
  2. 递推公式:dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
  3. 初始化:dp[0] = nums[0], dp[1] = max(dp[0], dp[1]);
  4. 遍历顺序:从前到后更新。

代码:

class Solution {
public:
    int rob(vector<int>& nums) {
        //当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。
        //dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        vector<int> dp(nums.size(),0);
        if(nums.size() == 1) return nums[0];
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

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

到了这里,关于【Day52】代码随想录之动态规划_打家劫舍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 代码随想录 day38 第九章 动态规划part01

    ●  理论基础 ●  509. 斐波那契数 ●  70. 爬楼梯 ●  746. 使用最小花费爬楼梯 理论基础 解决动态规划必须要想清楚的点 dp数组以及下标的含义 递推公式 dp数组如何初始化 遍历顺序 打印数组 检查结果 关联 leetcode 509. 斐波那契数 思路 动规五部曲 dp数组以及下标的含义

    2024年04月17日
    浏览(48)
  • 代码随想录Day_52打卡

    给你一个整数数组  nums  ,找到其中最长严格递增子序列的长度。 子序列  是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7]  是数组  [0,3,1,6,2,2,7]  的子序列。 事例: 思路:        使用动态规划,dp含义:dp[i]表示数

    2024年02月10日
    浏览(38)
  • 【Day42】代码随想录之动态规划0-1背包_416. 分割等和子集

    动态规划理论基础 动规五部曲: 确定dp数组 下标及dp[i] 的含义。 递推公式:比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。 初始化dp数组。 确定遍历顺序:从前到后or其他。 推导dp数组。 出现结果不正确: 打印dp日志和自己想的一样:递推公式、初始化或者遍历顺序出错。 打印

    2024年02月20日
    浏览(63)
  • 【Day45】代码随想录之动态规划part7—爬楼梯(进阶)、零钱兑换、完全平方数

    今天又是补打卡的一天,开冲!!! 今日任务: 70.爬楼梯(进阶) 322.零钱兑换 279.完全平方数 这道题之前做过一次,但是可以采用完全背包的问题来分析一遍。 卡玛网题目:【57.爬楼梯】 这个题目其实是更难了一点,因为前面的题目都是每次要不爬1阶楼梯,要不爬2阶楼

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

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

    2024年03月11日
    浏览(58)
  • 【Day53】代码随想录之动态规划part10——买卖股票的最佳时机、买卖股票的最佳时机II

    昨天已经把打家劫舍的问题解决了,最后一个题目涉及到树形dp比较难(等到二刷的时候再重点看下),今天的任务是解决股票问题。 今日任务: 121.买卖股票的最佳时机 122.买卖股票的最佳时机II Leetcode题目:【121.买卖股票的最佳时机】 因为此题中买卖股票只能买卖一次。

    2024年03月15日
    浏览(95)
  • 代码随想录 Day35 动态规划04 01背包问题和完全背包问题 LeetCode T416 分割等和子集

    说到背包问题大家都会想到使用动规的方式来求解,那么为什么用动规呢, dp数组代表什么呢 ? 初始化是什么 , 遍历方式又是什么 ,这篇文章笔者将详细讲解背包问题的经典例题0-1背包问题和完全背包问题的解题方式,希望能帮助到大家 有人一提到背包问题就只会使用动态规划来

    2024年02月06日
    浏览(71)
  • 【Day43】代码随想录之动态规划0-1背包_1049. 最后一块石头的重量 II_494. 目标和_ 474.一和零

    动态规划理论基础 动规五部曲: 确定dp数组 下标及dp[i] 的含义。 递推公式:比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。 初始化dp数组。 确定遍历顺序:从前到后or其他。 打印。 出现结果不正确: 打印dp日志和自己想的一样:递推公式、初始化或者遍历顺序出错。 打印dp日志和

    2024年02月22日
    浏览(48)
  • 代码随想录Day32 动态规划01 LeetCodeT509 斐波那契数列 T70 爬楼梯 T746 爬楼梯的最小消耗

    动态规划首先可以解决的问题有背包问题,打家劫舍问题,股票问题,子序列问题等,主要是将一个大的问题切分成多个重叠的子问题,所以动态规划一定是上一个状态递推过来的,有一个重要的 状态转移方程, 但是这也并不是解题的全部,我们将动态规划的题目基本分为五步来完成

    2024年02月06日
    浏览(68)
  • 代码随想录Day36 动态规划05 LeetCode T1049最后一块石头的重量II T494 目标和 T474 一和零

    理论基础  : 代码随想录Day34 LeetCode T343整数拆分 T96 不同的二叉搜索树-CSDN博客 1.明白dp数组的含义 2.明白递推公式的含义 3.初始化dp数组 4.注意dp数组的遍历顺序 5.打印dp数组排错 题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode) 这题我们仍然采用动规五部曲来写,这题和

    2024年02月06日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包