Leetcode题目198.打家劫舍(动态规划-简单)
2024-09-05 08:51:55
题目描述:
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
示例 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 。
思路分析:动态规划
动态规划方程:dp[n] = MAX( dp[n-1], dp[n-2] + num )
由于不可以在相邻的房屋闯入,所以在当前位置 n 房屋可盗窃的最大值,要么就是 n-1 房屋可盗窃的最大值,要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值,二者之间取最大值
举例来说:比如输入为[3,4,2]
1 号房间可盗窃最大值为 3 即为 dp[1]=3,2 号房间可盗窃最大值为 4 即为 dp[2]=4,3 号房间自身的值为 2即为 num=2,那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5,3 号房间可盗窃最大值为 5
class Solution {
public static int rob(int[] nums) { int len = nums.length;
if (len == 0) {
return 0;
}
int[] dp = new int[len + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= len; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i-1]);
}
return dp[len];
}
}
时间复杂度:O(n)
空间复杂度:O(n)
最新文章
- Android5.1.1源码 - zygote fork出的子进程如何权限降级
- BZOJ2408 混乱的置换
- BZOJ 2466: [中山市选2009]树
- [linux] Nginx编译安装错误error: the HTTP rewrite module requires the PCRE library
- C#的 构造函数 和 方法重载
- UVAlive3486_Cells
- mysql一个事务中有DDL语句的binlog情况
- 20145235 《Java程序设计》第4周学习总结
- bzoj4216 Pig
- EF 中更新模型的问题,这种错误(因为相同类型的其他实体已具有相同的主键值。)
- 【英语】Bingo口语笔记(40) - [aʊ]的发音规则
- 飘逸的python - 解决一个有限制的组合需求
- LINUX常用命令-系统配置篇(二)
- [置顶] js中如何复制一个对象,如何获取所有属性和属性对应的值
- MySQL InnoDB数据库备份与还原
- jenkins 杀死衍生进程
- SmtpDlg 调用SMTP
- IP 网际协议
- HTTP协议详解【转】
- Java并发编程:线程控制