力扣213. 打家劫舍 II---环形变线形+dp
发布日期:2021-06-28 15:43:57
浏览次数:3
分类:技术文章
本文共 759 字,大约阅读时间需要 2 分钟。
213. 打家劫舍 II
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,能够偷窃到的最高金额。
示例 1:输入:nums = [2,3,2]输出:3解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。示例 2:输入:nums = [1,2,3,1]输出:4解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。示例 3:输入:nums = [0]输出:0 提示:1 <= nums.length <= 1000 <= nums[i] <= 1000
题解:
详情见。
直接分解为第一个偷或不偷的情况,接着dp即可。 即注意x[i]为第一个房子偷的情况下后面对应房子序号为i时所能偷到的最大金额。 y[i]为第一个房子不偷的情况下后面对应房子序号为i时所能偷到的最大金额。代码:
int rob(int* nums, int numsSize){ if(numsSize==1) return nums[0]; int x[numsSize+1]; int y[numsSize+1]; x[0] = nums[0]; y[0] = 0; x[1] = nums[0]; y[1] = nums[1]; for(int i=2;i
转载地址:https://blog.csdn.net/xiangguang_fight/article/details/115716734 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月04日 15时08分49秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
linux文件系统挂载与卸除
2019-04-29
LVM逻辑卷管理
2019-04-29
node接受get及post请求参数
2019-04-29
go简单的struct用法
2019-04-29
js中let与箭头函数
2019-04-29
ajax上传附件
2019-04-29
ajax大文件分片上传服务器
2019-04-29
select绑定change事件
2019-04-29
beego简单分页
2019-04-29
beego封装简单分页类
2019-04-29
nginx代理访问go web
2019-04-29
mysql的group_concat结合group by使用方法
2019-04-29
layui富文本编辑器的使用
2019-04-29
laydate日期插件时间
2019-04-29
h5页面微信分享代码
2019-04-29
phpqrcode生成二维码及使用方法
2019-04-29
php获取指定日期的上一个月和下一个月的日期
2019-04-29
jsp脚本、jsp表达式、jsp声明三者的区别。
2019-04-29
python网页解析器
2019-04-29
linux安装svn并设置自启动
2019-04-29