[LeetCode]337. 打家劫舍 III_c语言你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是-程序员宅基地

技术标签: DP  数据结构  

题目描述:在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。
计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。
题目链接:337. 打家劫舍 III

树形dp,用map结构存储局部最优解。
map[x]表示以节点x为根节点的子树中能盗取的最高金额。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    
    map<TreeNode *,int> f;
public:
    int dp(TreeNode* x){
    
        if (x==NULL) return 0;
        if (f.count(x)) return f[x]; //已有答案不需重复搜索
        int ans=x->val;
        if (x->left!=NULL) ans+=dp(x->left->left)+dp(x->left->right);
        if (x->right!=NULL) ans+=dp(x->right->left)+dp(x->right->right);
        ans=max(ans,dp(x->left)+dp(x->right));
        f[x]=ans;
        return ans;
    }
    int rob(TreeNode* root) {
    
        return dp(root);
    }
};
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_39947473/article/details/91353451

智能推荐

vue添加nrm失败throw new ERR_INVALID_ARG_TYPE(name, ‘string‘, value);_安装nrm后 添加源失败-程序员宅基地

文章浏览阅读252次。问题使用nrm添加公司私源失败,报错throw new ERR_INVALID_ARG_TYPE(name, 'string', value);解决1、鼠标移到TypeError第四行,(C:\Users\zhanshiyu\AppData\Roaming\npm\node_modules\nrm\cli.js:17:20),Ctrl+鼠标点击,进入cli.js页面。2、替换第十七行代码:// const NRMRC = path.join(process.env.HOME, '.nrmrc')_安装nrm后 添加源失败

ffmpeg使用_fmpeg-4.2.1-win32-shared.zip-程序员宅基地

文章浏览阅读304次。参考ffmpeg常用命令ffmpeg参数中文详细解释[总结]FFMPEG视音频编解码零基础学习方法一、安装打开https://ffmpeg.zeranoe.com/builds/,该网站中的FFMPEG分为3个版本:Static,Shared,Dev。前两个版本可以直接在命令行中使用,他们的区别在于:Static里面只有3个应用程序:ffmpeg.exe,ffplay.exe..._fmpeg-4.2.1-win32-shared.zip

QTableWidget设置为不可以编辑状态_如何qt的ui界面,使得别人无法修改-程序员宅基地

文章浏览阅读1w次,点赞3次,收藏4次。在Qtablewidget 展示的时候,有时候我们不希望表格的内容被篡改,于是我们可以设置表格的属性选中需要的设置的表格,然后在筛选框中输入edit如下图所示勾选NoEditTriggers就好了_如何qt的ui界面,使得别人无法修改

【bzoj3747】[POI2015]Kinoman-程序员宅基地

文章浏览阅读59次。题解:水题从左向右维护以每一个作为右端点的最大值线段树维护代码:#include <bits/stdc++.h>using namespace std;#define rint register ll#define IL inline#define rep(i,h,t) for (rint i=h;i<=t;i++)#define..._从左向右维护以每一个作为右端点的最大值 设记录第 i 天的电影下次播放时间 枚举

Linux用户管理详解_linux登录qq是什么意思-程序员宅基地

文章浏览阅读448次。Linux用户管理用户基本概念什么是用户用户指的是能够正常登录Linux或Windows系统,比如:登录QQ的用户、登入王者荣耀的用户、等等[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nz1edsjq-1626145230283)(C:\Users\李开开\AppData\Roaming\Typora\typora-user-images\image-20210712171546940.png)]为什么需要用户系统上的每一个进程(运行的程序),都_linux登录qq是什么意思

Unity中协程里Animator获取状态一些笔记_getanimatortransitioninfo-程序员宅基地

文章浏览阅读4.5k次,点赞4次,收藏7次。最近用Animator获取状态各种获取错误,所以记一下笔记Animator中可以获取三种不同的状态:GetCurrentAnimatorStateInfo 获取正确的状态机状态GetNextAnimatorStateInfo 获取下一个状态机的状态GetAnimatorTransitionInfo 获取状态机的过渡状态动画同步是在帧最前,而协程是在帧的最后调用。所以切换状态后在协程获取状..._getanimatortransitioninfo

随便推点

scrollview 嵌套 recycleview 问题 gridlayout_recycleview 网格形式 和scrollview-程序员宅基地

文章浏览阅读551次。1.使用NestedScrollView2.recycle.setHasFixedSize(true); recycle.setNestedScrollingEnabled(false);_recycleview 网格形式 和scrollview

git撤销本地所有修改_git 回退所有的修改-程序员宅基地

文章浏览阅读3.3k次。git撤销本地所有修改 git checkout ._git 回退所有的修改

signature=714e576fcd503d3d5c4bb0e0722ca7f2,System and method for the secure enrollment of devices wi...-程序员宅基地

文章浏览阅读100次。摘要:Enrolling devices with a clearinghouse server for Internet telephony and multimedia communications. Enrollment can be the process of taking a network device (such as a router, gateway, gatekeeper, ...

《iOS 9 开发指南》——第1章,第1.3节工欲善其事,必先利其器——搭建开发环境...-程序员宅基地

文章浏览阅读202次。本节书摘来自异步社区《iOS 9 开发指南》一书中的第1章,第1.3节工欲善其事,必先利其器——搭建开发环境,作者 管蕾,更多章节内容可以访问云栖社区“异步社区”公众号查看1.3 工欲善其事,必先利其器——搭建开发环境iOS 9 开发指南图片 2 知识点讲解:光盘:视频知识点第1章搭建开发环境.mp4学习iOS 9开发也离不开好的开发工具的帮助,如果使..._(1)下载完成后单击打开下载的“.dmg”格式文件,然后双击xcode文件开始安装。

iView 3.3.2 发布,基于 Vue.js 的企业级 UI 组件库-程序员宅基地

文章浏览阅读115次。开发四年只会写业务代码,分布式高并发都不会还做程序员? iView 3.3.2 发布了,iView 是一套基于 Vue..._iview 3.2.2

详解not in与not exists的区别与用法(not in的性能并不差!)-程序员宅基地

文章浏览阅读93次。2019独角兽企业重金招聘Python工程师标准>>> ..._predicate not in查询

推荐文章

热门文章

相关标签