LeetCode-198. House Robber

落日映苍穹つ 2022-08-20 12:28 1阅读 0赞

Problem:

> 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.

Analysis:  
这个问题是典型的简单的DP（动态规划）问题，主要思想是找到逻辑关系，通过上述题意可以得到递推关系：maxv=Math.max(maxv\[i-2\]+nums\[i\],maxv\[i-1\]),这个递推关系的意思是：这个房间可以得到的最大抢劫数额为（这个房间不相邻的上一个房间最大抢劫数额+本房间的数额）与（上一个相邻的房间的最大抢劫数额）的最大值。  
Anwser:

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

本题经验总结：

1.  Java数组定义方法：int\[\] maxv=new int\[nums.length\];
2.  要考虑给定数组为空和数组只有一个值得情况。所以要有if (nums.length==0) return 0;

发表评论取消回复

表情：

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

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

相关阅读

相关 198. House Robber

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

阳光穿透心脏的1/2处/ 2022年08月21日 11:41/ 0 赞/ 140 阅读

相关 LeetCode-198. House Robber

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

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

相关 leetCode198-House Robber

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

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

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

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

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

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

相关（Java）leetcode-198 House Robber（打家劫舍）

更多LeetCode题解，可移步[我的解题记录][Link 1]，持续更新中~ 题目描述你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的

客官°小女子只卖身不卖艺/ 2022年03月06日 12:08/ 0 赞/ 194 阅读

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

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