[LeetCode]198. 打家劫舍(DP)
2024-09-07 17:41:25
题目
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
示例 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 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/house-robber
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
dp
代码
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= nums.length; ++i) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i-1]);
}
return dp[nums.length];
}
}
最新文章
- JS 怎么控制某个div的滚动条滚动到顶部? (已解决)
- Could not publish server configuration for Tomcat v6.0 Server at localhost.
- Linux之硬件管理(不断更新中)
- Bootstrap_导航
- AjaxUploader使用
- 是否用new来新建对象
- 共享内存 share pool (2):BUCKET /FREE LISTS /RESERVED FREE LISTS /UNPINNED RECREATABLE CHUNKS (lru first)
- Kali Linux 优化过程
- POJ No.3680 Intervals
- 递归:这帮坑爹的小兔崽子 - 零基础入门学习Python023
- 使用AFNetworking请求新浪微博数据接口出错解决办法
- es6对象字面量增强
- command not found所有执行命令总是报找不到
- C#设计模式之2:单例模式
- Substring方法(C#,JS,Java,SQL)的区别
- ffmpeg 在ubuntu上编译环境搭建和开发
- android逆向四则运算
- 【刷题】BZOJ 2194 快速傅立叶之二
- 一个GIS系统需具备的功能
- 114. Unique Paths [by Java]
热门文章
- 数值分析案例:Newton插值预测2019城市(Asian)温度、Crout求解城市等温性的因素系数
- 洛谷P1057 传球游戏 完美错觉(完美错解)
- 如何理解算法时间复杂度的表示法O(n&#178;)、O(n)、O(1)、O(nlogn)等?
- linux驱动之内核多线程(二)
- docker 启动容器失败 id already in use
- Python 抓包程序(pypcap)
- Linux用户和组密令大全
- 牛客网PAT练习场-有几个PAT
- muduo源码解析8-date类
- IDEA 代码自动补全/自动联想 功能