力扣题解 - 198. 打家劫舍
2020-05-29 16:06:36来源:博客园 阅读 ()
力扣题解 - 198. 打家劫舍
题目描述
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
? 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
1、思路
先说下自己的错误思路,一看是个简单的题就自以为是了,以为就是奇数位置和偶数位置和的最大值,然而没想到[2,1,1,2]这个样例,这个样例最大值是4,所以下次做题一定要认真,不能想的太简单了。
再来说正确的思路吧:仔细想了想发现是一个简单的动态规划。把问题细化,对于第i个房间有两个选择。
选择1:偷第i个房间的钱,如果要偷的话那么就不能偷第i-1个房间,所以总金额应该是 前i-2个房间的最大值+i房间的金额。
选择2:不偷,那么结果就是前i-1个房间的最大值
得到转移方程:
dp[i] = Math.max(dp[i-1],d[i-2]+nums[i]);
对于只有一个房间,最大值就是这个房间的金额
有两个房间,就是这两个房间的最大值。
2、代码
class Solution {
public int rob(int[] nums) {
if(nums.length == 0 || nums == null) return 0;
int[] dp = new int[nums.length];
if(nums.length == 1) return nums[0];
if(nums.length == 2) return Math.max(nums[0],nums[1]);
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i = 2; i < nums.length; i++){
dp[i] = Math.max(nums[i] + dp[i-2],dp[i-1]);
}
return dp[nums.length-1];
}
}
原文链接:https://www.cnblogs.com/Z-Dey/p/12990107.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 力扣题解 - 739. 每日温度 2020-06-11
- JVM常见面试题解析 2020-06-11
- Java架构面试必知必会的微服务面试题解析 2020-05-19
- 2020最新高并发架构消息队列面试题解析(建议收藏) 2020-04-17
- 2020年最全java面试真题解析(980道),你没见过的面试题都 2020-04-15
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash