[LeetCode] House Robber

ゝ一世哀愁。 2022-08-05 01:00 137阅读 0赞

**House Robber **

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.

思路：  
     1、条件：不能同时获取相邻的金钱  
     2、动态规划：当前节点的金钱数量等于当前的金额加上前面的金额最大值  
     3、最后遍历一次求出最大值即为结果

想到一种先排序，把下标记录下来，然后从后往前遍历，将下标差不为1的相加，wrong answer ，后面才想到用动态规划，看来动态规划还是不太熟

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

发表评论取消回复

表情：

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

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

相关阅读

相关 leetCode198-House Robber

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

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

相关 [LeetCode] House Robber

House Robber You are a professional robber planning to rob houses along a street.

ゝ一世哀愁。/ 2022年08月05日 01:00/ 0 赞/ 138 阅读

相关 leetcode House Robber II

题目 Note: This is an extension of House Robber. After robbing those houses on that st

小鱼儿/ 2022年08月01日 11:08/ 0 赞/ 125 阅读

相关 leetcode House Robber

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

快来打我*/ 2022年08月01日 11:08/ 0 赞/ 140 阅读

相关 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 赞/ 145 阅读

相关 LeetCode198—House Robber

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

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

相关 [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 赞/ 137 阅读

相关 [LeetCode] House Robber 打家劫舍||

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系

怼烎@/ 2022年05月18日 07:57/ 0 赞/ 158 阅读

相关 [LeetCode] House Robber 打家劫舍

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

- 日理万妓/ 2022年05月18日 02:57/ 0 赞/ 158 阅读

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

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

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