[LeetCode] 198. 打家劫舍 ☆(动态规划)
2024-09-08 04:35:46
描述
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
示例 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 。
解析
相邻房间不能去,所以房间n获取到的最大值,要么是房间n - 2的最大值加上房间n的值,要么是房间n - 1的最大值。
所以,提取出的公式:f(n) = max( f(n - 2) + nums[n], f(n - 1) )
代码
基本代码
public int rob(int[] nums) {
if (null == nums || nums.length == 0) {
return 0;
} else if (nums.length == 1) {
return nums[0];
} else if (nums.length == 2) {
return Math.max(nums[0], nums[1]);
}
int[] array = new int[nums.length];
array[0] = nums[0];
array[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
array[i] = Math.max(array[i - 1], array[i - 2] + nums[i]);
}
return array[array.length - 1];
}
基本优化
由于只需要数组前2个值,所以可以不用数组,直接用2个数字代替。
public static int rob(int[] nums) {
if (null == nums || nums.length == 0) {
return 0;
} else if (nums.length == 1) {
return nums[0];
} else if (nums.length == 2) {
return Math.max(nums[0], nums[1]);
}
int preVal = nums[0];
int curVal = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int temp = Math.max(curVal, preVal + nums[i]);
preVal = curVal;
curVal = temp;
}
return curVal;
}
相似题
[LeetCode] 213. 打家劫舍II ☆☆☆(动态规划)
[LeetCode] 337. 打家劫舍III ☆☆☆(动态规划)
最新文章
- Mac AppleScript 自动完成按键
- js的this上下文的坑
- Windows Phone 开发——相机功能开发
- 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
- 2026-Keroro侵略地球
- vs212创建mvc3项目,添加ADO.NET实体数据模型时产生 XXXX.Desiger.cs 文件为空
- ZOJ3805:Machine
- c++ 计算程序运行时间
- 201521123045java课程设计---定时器
- StringBuffer的替换和反转和截取功能
- 关于mule中Spring使用中的一个问题
- JDK安装、变量、变量的分类
- 【bzoj 3495】PA2010 Riddle
- 学习笔记-ResNet网络
- Bokeh
- Jupyter notebook安装
- 解决Xcode删除文件后missing file警告
- Entity Framework 学习
- Oracle12c中容错&;amp;性能新特性之表空间组
- Oracle12c Client安装出现";[INS-30131]";错误“请确保当前用户具有访问临时位置所需的权限”解决办法之完整版