LeetCode : 198. House Robber 入室抢劫

深藏阁楼爱情的钟 2021-06-24 16:11 343阅读 0赞

**试题**  
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: \[1,2,3,1\]  
Output: 4  
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).  
Total amount you can rob = 1 + 3 = 4.  
Example 2:

Input: \[2,7,9,3,1\]  
Output: 12  
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).  
Total amount you can rob = 2 + 9 + 1 = 12.  
**代码**  
以当前的位置最大可以获得的钱作为动归。存在两种情况：抢劫当前位置和不抢劫当前位置。

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

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-198. House Robber

Problem: > You are a professional robber planning to rob houses along a street. > Eac

落日映苍穹つ/ 2022年08月20日 12:28/ 0 赞/ 21 阅读

相关 leetCode198-House Robber

题目： You are a professional robber planning to rob houses along a street. Each house has

今天药忘吃喽~/ 2022年08月07日 10:55/ 0 赞/ 151 阅读

相关 leetcode 198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a ce

旧城等待，/ 2022年07月28日 01:09/ 0 赞/ 163 阅读

相关 LeetCode198—House Robber

原题 [原题链接][Link 1] You are a professional robber planning to rob houses along a stre

傷城~/ 2022年07月11日 12:22/ 0 赞/ 144 阅读

相关 [leetcode]: 198. House Robber

1.题目 You are a professional robber planning to rob houses along a street. Each house

ゞ浴缸里的玫瑰/ 2022年06月15日 09:14/ 0 赞/ 152 阅读

相关 leetcode 198. House Robber 入室抢劫 + DP动态规划求解

You are a professional robber planning to rob houses along a street. Each house has a ce

古城微笑少年丶/ 2022年06月08日 08:23/ 0 赞/ 174 阅读

相关 LeetCode 198.House Robber (打家劫舍)

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

小咪咪/ 2022年04月15日 00:49/ 0 赞/ 170 阅读

相关 LeetCode：198. House Robber（房子抢劫问题）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。 > > 这博客是记录我学习的点点滴滴，如果您对 Python、Java

桃扇骨/ 2022年04月11日 09:55/ 0 赞/ 178 阅读

相关 198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a ce

た入场券/ 2022年03月02日 08:10/ 0 赞/ 212 阅读

相关 LeetCode : 198. House Robber 入室抢劫

试题 You are a professional robber planning to rob houses along a street. Each house has

深藏阁楼爱情的钟/ 2021年06月24日 16:11/ 0 赞/ 344 阅读