力扣213. 打家劫舍 II---环形变线形+dp
发布日期:2021-06-28 15:43:57
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月14日 03时45分24秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【基础+实战】JVM原理及优化系列之一:JVM体系结构
2019-04-29
【基础+实战】JVM原理及优化系列之二:JVM内存管理
2019-04-29
【基础+实战】JVM原理及优化系列之三:JVM垃圾收集器
2019-04-29
【基础+实战】JVM原理及优化系列之四:JVM参数说明
2019-04-29
【基础+实战】JVM原理及优化系列之五:JVM默认设置
2019-04-29
【基础+实战】JVM原理及优化系列之六:JVM主要调优参数
2019-04-29
【基础+实战】JVM原理及优化系列之十:JVM内存泄漏专题实战
2019-04-29
Redis高可用架构 (redis主从+sentinel)
2019-04-29
【重磅推出】性能提升100倍的性能测试监控优化方法
2019-04-29
Spring cloud微服务框架简介
2019-04-29
【实用】Redis各种存储结构使用场景
2019-04-29
【实用】Redis高级功能
2019-04-29
DevOps八荣八耻了解下,哈哈~
2019-04-29
API Gateway(API网关)介绍
2019-04-29
【免费】少儿编程社区,Scratch中文社区,少儿编程学习交流平台上线~~~
2019-04-29
JavaMail关于使用qq企业邮箱发邮件踩过的坑
2019-04-29
log4j2异步发送error日志邮件配置
2019-04-29
redis setnx解决定时任务多节点部署并发问题(分布式锁)
2019-04-29
spring boot使用redis解决session双机问题
2019-04-29