代码随想录算法训练营DAY47|C++动态规划Part8|198.打家劫舍、213.打家劫舍II、198.打家劫舍III

2024-05-09 01:36
文章标签 算法 随想录 代码 动态 规划 c++ ii 训练营 iii 打家劫舍 213 198 day47 part8

本文主要是介绍代码随想录算法训练营DAY47|C++动态规划Part8|198.打家劫舍、213.打家劫舍II、198.打家劫舍III，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 198.打家劫舍
    • 思路
    • CPP代码
  • ⭐️213.打家劫舍II
    • 解决环的问题
    • 思路
    • 总结
    • CPP代码
  • ⭐️198.打家劫舍III
    • 思路
      • 递归三部曲——确定参数和返回值
      • 递归三部曲——确定终止条件
      • 递归三部曲——确定单层遍历的逻辑
    • 打印dp数组
    • CPP代码
    • 暴力递归
    • 记忆化递归

198.打家劫舍

力扣题目链接

文章讲解：198.打家劫舍

视频讲解：动态规划，偷不偷这个房间呢？| LeetCode：198.打家劫舍
状态：由于我们偷当前房屋，肯定会影响后续的偷窃活动，所以本题肯定是动态规划。总体来说本题还不算难，但是非常重要！

这里把题目再抽象一下：

偷钱币的规则——相邻房间不能偷，然后随便怎么偷都行

本题最大的难点就是，虽说相邻房间不能偷，但是剩下的都可以偷，甚至隔好几个房间再偷。那么当前这个房间到底偷不偷呢？这是最关键的点

其实我们当前房间偷不偷本质上依赖于我们前一个房间和前两个房间偷与不偷的状态，如果前一个房间被偷了，那本房间绝对不能偷，如果偷了前两个房间，那么这个房间可以偷也可以不偷，所以当前房间偷不偷和前一个和前两个房间的状态是由关系的，这个关系也就是我们的递推关系。

思路

  • dp数组的含义

我们考虑数组下标i（包含下标i），它所偷的最大的钱币就是dp[i]，最终的结果在dp[nums.size() - 1]

  • 递推公式

对于房间i，无非就是偷或者不偷，

如果我们明确要偷i，那么i前面的那个房间是一定不考虑的，所以最多只能考虑到dp[i-2]，其中的dp[i-2]表示在i-2（包含）及之前的所有房间所能偷的最大金币数量再加上i房间的金币数量，所以递推公式

d p [ i − 2 ] + n u m s [ i ] dp[i-2]+nums[i] dp[i−2]+nums[i]

如果我们明确不偷i，此时我们就可以考虑i-1以及i-1之前的所有房间所能偷的最大金币数量，所以递推公式

d p [ i − 1 ] dp[i-1] dp[i−1]

综上所示，递推公式为

dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
  • 初始化

从递归公式可以看出来dp[i]是由dp[i-2]和dp[i-1]推导出来的，所以递推公式的基础就是dp[0]、dp[1]。

很明显dp[0]=nums[0] ，至于dp[1]=max(nums[0], nums[1])

非零和非一下标初始化成0即可

  • 遍历顺序

    这里遍历顺序就很简单了，没什么讲究

for (int i = 2; i < nums.size(); i++)
  • 打印

CPP代码

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;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[nums.size() - 1];}
};

⭐️213.打家劫舍II

力扣题目链接

文章讲解：213.打家劫舍II

视频讲解：动态规划，房间连成环了那还偷不偷呢？| LeetCode：213.打家劫舍II
状态：这里成环的处理逻辑还是很牛逼的，并且非常通用，需要重点解决

本题与198.打家劫舍有什么区别呢？唯一的区看别就是本题把线性数组首尾相连连成环了，这会导致规则有什么样的变化呢？

  • 相邻房间不偷，这是肯定的
  • 首尾元素只能选一个偷。因为本题首尾相连了！

一旦连成环就很容易懵，本题还有起点和终点吗？起点和终点应该如何选呢？

解决环的问题

如果连成环的话，首尾元素如果要选的话只能选择一个，要不选首元素要不尾元素，要不都不选。其实本质上我们可以划分成三个情况，这里拿[1, 6, 1, 9, 1]举例

  • 情况一：不考虑首元素也不考虑尾元素，只考虑中间的[6, 1, 9]数组范围

此时，该数组变成了一个线性数组，所以我们其实可以用线性数组的方式来解决本题，一下就变成了198.打家劫舍

  • 情况二：考虑首元素，不考虑尾元素了，即考虑[1, 6, 1, 9]数组范围。所以本题仍然能变成一个线性数组
  • 情况三：考虑尾元素，不考虑首元素了，即考虑[6, 1, 9, 1]数组范围。所以仍然变成一个线性数组解体

本题中的考虑首位元素并不代表我一定会选择首元素或尾元素，具体的选择是由递推公式决定的

现在再来分析一下这三种情况，从元素情况其实就可以看出，其实情况二和情况三已经包含了情况一的中间元素了。

所以综上所述：我们只要求情况二和情况三的最优解，然后取一个最大值就行

思路

上文中其实已经阐明了大部分的思路，现在我们的情况二和情况三已经是线性数组了，我们只需要把情况二[1, 6, 1, 9]传到我们的198.打家劫舍函数中，然后把情况三传到198.打家劫舍函数，取一个max。

总结

我们竟然把一个环形数组的题解耦成了一个线性数组！卡哥牛逼！

CPP代码

// 注意注释中的情况二情况三，以及把198.打家劫舍的代码抽离出来了
class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2); // 情况二int result2 = robRange(nums, 1, nums.size() - 1); // 情况三return max(result1, result2);}// 198.打家劫舍的逻辑int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp(nums.size());dp[start] = nums[start];dp[start + 1] = max(nums[start], nums[start + 1]);for (int i = start + 2; i <= end; i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[end];}
};

⭐️198.打家劫舍III

力扣题目链接

文章讲解：198.打家劫舍III

视频讲解：动态规划，房间连成树了，偷不偷呢？| LeetCode：337.打家劫舍3

状态：入门级树形dp，需要在二叉树中进行一个状态转移。只能说卡哥太牛逼了，这题的讲解真的是绝

基本规则和198.打家劫舍一样，只不过我们本题中数据结构变成了一个二叉树。

本题如果对二叉树不够了解，对二叉树的遍历不够娴熟的话，基本就是寄。

所以本题的思路也应该是以递归三部曲为主旋律，穿插动态规划五部曲的过程

思路

本文以root=[3, 4, 5, 1, 3, 5, 1]为例，

本题既然是遍历树形结构，那么肯定逃不开递归，所以本质是在单层递归逻辑中采用了动态规划的相关思想。

递归三部曲——确定参数和返回值

参数可能还懵懵懂懂能猜到，肯定是传入根结点！

那返回值是什么呢？dp数组是什么呢？如何融入树形遍历中呢？

首先最主要的问题肯定是解决dp数组的含义，在树形结构的递归遍历中，有一个最基本的思想，也就是不同的遍历方法可以去处理不同的逻辑。本题中，如果我们想偷当前节点，那么相邻结点也就是左右孩子节点肯定不能偷；如果偷左右孩子结点，那么当前节点就不能偷。所以肯定是用后序遍历，因为我们的当前结点的状态只要根据左右孩子的状态来的。

总而言之，这种情况最好的方法就是，用dp数组去定义每个结点的状态。

  • 确定dp数组的含义

每个节点只有两个状态，也就是说节点偷还是不偷，所以用一个长度为2的一维dp数组**dp[0]表示不偷当前节点情况的最大价值，dp[1]表示偷**当前结点情况的最大价值。总而言之就是每一个结点，都存在这样一个dp数组状态

  • dp数组的递推公式

本题使用的是后序遍历的方式，由底向上推，最后就有根结点是偷还是不偷的两个状态，那我们最终的结果就是根结点偷还是不偷的两个状态我们取一个最大值，那这个就是我们最后的结果。

那么我们定义当前节点左右孩子的dp数组状态为leftdp和rightdp。

再回到当前节点偷与不偷，当然选一个dp数组的最大值，所要要定义一个value1表示偷当前结点我们取得的最大钱币，那么如果我们偷了当前结点，那么本节点的左右孩子就一定不能偷了，那么我们要计算不偷左孩子能得到的最大钱币加上不偷右孩子能得到的最大钱币；

int value1 = cur->val + leftdp[0] + rightdp[0]

好了，现在我们必须要考虑偷左右孩子的情况了，如果偷左右任意一个孩子的话，那我们就不能偷当前结点。 再一个，左孩子偷不偷不是由我们去决定的，而是由leftdp[0]和leftdp[1]谁大就选哪个；右孩子偷还是不偷也是一样的道理，并且左右孩子是可以同时偷的，因为他们不算相邻结点。所以以代码如下：

int value2 = max(leftdp[0], leftdp[1]) + max(rightdp[0], rightdp[1]);

此时，我得到了两个状态value1和value2,value1是我偷当前结点的结果，value2是我不偷当前结点的结果，那么当前状态的偷和不偷就出来了，所以我们返回什么呢？

// 返回当前节点的dp数组
return {value2, value1} //{不偷，偷}

递归三部曲——确定终止条件

if (cur == NULL) return vector<int> (0, 0); //本质上是返回空间的dp数组的状态

如果当前节点是NULL的话，也就是我们此时遍历到了空节点，我们此时偷与不偷其实都是0，所以要返回一个元素都是0的dp数组。

递归三部曲——确定单层遍历的逻辑

我们已经在递归三部曲——确定参数和返回值：确定dp数组的递推公式中讲完了。

打印dp数组

以下图为例：

各个节点的dp数组为：（两列分别为dp[0]、dp[1]，行数为后序遍历的顺序）

CPP代码

class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}//长度为2的数组， 0:不偷 1:偷vector<int> robTree (TreeNode* cur) {if (cur == NULL) return vector<int> {0, 0};vector<int> leftDp = robTree(cur->left);vector<int> rightDp = robTree(cur->right);//偷cur,那么就不能偷左右结点。int val0 = cur->val + leftDp[0] + rightDp[0];//不偷cur，那么可以偷也可以不偷左右结点，则取较大的情况int val1 = max(leftDp[0], leftDp[1]) + max(rightDp[0], rightDp[1]);return {val1, val0};}
};

暴力递归

这里介绍一下暴力递归的办法，我觉得有利于加深树形dp的理解

int rob(TreeNode* root) {if(!root) return 0; //无结点if (!root->right && !root->left) return root->val;   //只有根结点//偷父节点int val1 = root->val;if (root->left) val1 += rob(root->left->left) + rot(root->left->right);if (root->left) val1 += rob(root->right->left) + rot(root->right->right);//不偷父节点int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子return max(val1, val2);

时间复杂度： O ( n 2 ) O(n^2) O(n2)
空间复杂度： O ( l o g n ) O(logn) O(logn)

记忆化递归

在暴力解法中，由于每个节点被访问多次（每次父节点考虑偷或不偷时），整体时间复杂度是指数级的。

所以我们可以用一个map把计算过的结果保存一下，那么计算过孙子节点，那么计算孩子节点的时候可以复用结果。
最核心的代码:

if (umap[root]) return umap[root];
...
umap[root] = max(val1, val2);

class Solution {
public:unordered_map<TreeNode*, int> umap; //记录计算过的结果int rob(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return root->val;if (umap[root]) return umap[root];  //如果umap里已经有记录了则直接返回// 偷父节点int val1 = root->val;if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->leftif (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right// 不偷父节点int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子umap[root] = max(val1, val2); // umap记录一下结果return max(val1, val2);}
};

这篇关于代码随想录算法训练营DAY47|C++动态规划Part8|198.打家劫舍、213.打家劫舍II、198.打家劫舍III的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/972022。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2