【动态规划】198. 打家劫舍

迈不过友情╰ 2022-11-25 00:49 53阅读 0赞

> ☞梦想进大厂的一只程序猿☜  
>   
> ☞期望毕业前力扣刷够400题☜  
>   
> ☞正在复习数据结构和算法☜  
>   
> ☞博客地址：[https://www.huangliangshuai.com/][https_www.huangliangshuai.com]☜  
>

# 1. 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]

# 2. 题目分析 #

1.  经典的DP问题，也是DP的入门。**条件：小偷不能偷相邻的房间**。
2.  如果我们当前对于最后一户人家，我们决定偷他：  
    那我们获取的最大利益是：`nums[i] + opt[i - 2]` **这里的opt代表，我们从第一家偷到第几家的收益**  
    如果我们不偷的话，那我们获取的最大利益是：opt\[i - 1\]  
    我们可以列关系式：`opt[i] = Math.max(opt[i-1], nums[i] + opt[i-2]);`
3.  我们需要找到出口，这个题目的出口比较简单，也就是`opt[0] = nums[0]、opt[1] = Math.max(nums[0], nums[1]);`

# 3. 题目代码 #

class Solution {
        
        public int rob(int[] nums) {
        
            int[] opt = new int[nums.length];
    		if (nums.length == 0) {
        
    			return 0;
    		}
    		if (nums.length == 1) {
        
    			return nums[0];
    		}
    		opt[0] = nums[0];
    		opt[1] = Math.max(opt[0], nums[1]);
    		for (int i = 2; i < nums.length; i++) {
        
    			opt[i] = Math.max(opt[i - 1], nums[i] + opt[i - 2]);
    		}
    		return opt[nums.length - 1];
        }
    }

[https_www.huangliangshuai.com]: https://www.huangliangshuai.com/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20221124/7a99ccb7d6884e5484c0b5a4d03e1b5f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，53人围观）

还没有评论，来说两句吧...

相关阅读

相关 198. 打家劫舍

198. 打家劫舍你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同

蔚落/ 2024年03月30日 15:10/ 0 赞/ 59 阅读

相关 leetcode: 198. 打家劫舍

链接：https://leetcode-cn.com/problems/house-robber/ 设dp\[i - 1\]表示前 i - 1 间房子能偷窃到的最高金额。

绝地灬酷狼/ 2023年01月18日 09:26/ 0 赞/ 9 阅读

相关【必备算法】动态规划：LeetCode题（二）：198. 打家劫舍，213. 打家劫舍 II

[198. 打家劫舍¹][198.] 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果

╰+攻爆jí腚メ/ 2022年12月18日 01:00/ 0 赞/ 127 阅读

相关【leetcode.198】打家劫舍

一、题目描述你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上

野性酷女/ 2022年12月10日 01:22/ 0 赞/ 122 阅读

相关【动态规划】198. 打家劫舍

> ☞梦想进大厂的一只程序猿☜ > > ☞期望毕业前力扣刷够400题☜ > > ☞正在复习数据结构和算法☜ > > ☞博客地址：[https://

迈不过友情╰/ 2022年11月25日 00:49/ 0 赞/ 54 阅读

相关 198. 打家劫舍

> 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统

╰+攻爆jí腚メ/ 2022年10月09日 00:35/ 0 赞/ 158 阅读

相关 198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自

分手后的思念是犯贱/ 2022年08月31日 11:07/ 0 赞/ 135 阅读

相关 leetcode198打家劫舍

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

向右看齐/ 2022年08月29日 11:57/ 0 赞/ 141 阅读

相关 leetcode 198 打家劫舍

前言题目：[198. 打家劫舍][198.] 参考题解：[打家劫舍-代码随想录][-] -------------------- 提交代码动态规划。递推公

左手的ㄟ右手/ 2022年08月28日 03:52/ 0 赞/ 226 阅读

相关 LeetCode198:打家劫舍

实验平台：[LeetCode][] 代码地址：[my github][] 题目描述： ![这里写图片描述][70] 示例： ![这里写图片描述][70 1]

小灰灰/ 2022年05月17日 21:27/ 0 赞/ 160 阅读