[LeetCode]198. 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.

大致意思就是你是职业窃贼,计划沿着一条街道抢劫,每个房子都藏有固定价值的钱,唯一的约束条件就是你不能每一房子都去抢劫,因为相邻的房子有相连接的安全系统,如果相邻的房子都被抢了,安全系统就会自动联系警察.

现在给定一组非负数组代表每个房子所藏有钱的数量,如何在不被报警的情况下抢到最大值的钱.

看到题目结尾说要最大值,第一反应就是可以用暴力搜索解决这个问题.

class Solution {
    
    int maxMoney(int index, int[] nums) {
			if (index < 0) {
				return 0;
			}
			return Math.max(nums[index] + maxMoney(index - 2, nums), maxMoney(index - 1, nums));
		}

		public int rob(int[] nums) {
			return maxMoney(nums.length - 1, nums);
		}
}

主要逻辑就在maxMoney(int index, int[] nums)中,index代表你抢到第几家,后续return暴力搜索结果的过程,根据条件限制,如果你抢了第index家,那么你最近能抢的一家就为index-2,那么当你抢到第index家时,你的总钱数就是nums[index](第index家的钱数量)+maxMoney(index - 2, nums)(最近1次抢的家的钱的总数)和如果你不抢第index家时,那么你的总钱数就是maxMoney(index - 1, nums),在这2个总数中间取1个更大的值.

仔细思考之后,这道题用Dynamic Programming也能做,而且更简单.我们通过这道题的描述.

如果index=0时;代表要抢第1家,那么之后能抢的就有{2,3,4,5,6...};
如果index=1时;代表要抢第2家,那么之后能抢的就有{3,4,5,6,7...};
如果index=2时;代表要抢第3家,那么之后能抢的就有{4,5,6,7,8...};
如果index=3时;代表要抢第4家,那么之后能抢的就有{5,6,7,8,9...};
.
.
...
如果index=nums.length-2时;代表要抢倒数第2家,那么之后没有可以抢的家;
如果index=nums.length-1时;代表要抢倒数第1家,那么之后没有可以抢的家;

如果我们用数组dp[]来表示抢到钱的总数最大值,那么dp[index],就表示从第0家抢到第index家的抢钱总数最大值.

1. 当只有1家时,dp[0]=num[0],最大值就是result=dp[0],因为只有1家能抢;
2. 当只有2家时,那么抢的钱只能在在这2家里面选,dp[0]=num[0],dp[1]=num[1],那么result=Max(dp[0],dp[1]);
3. 当有3家时,就会出现2种情况,抢第一家和第三家,或者只强第二家.那么dp[2]就有:$$result= \begin{cases}dp\left[ 0\right] +dp\left[ 2\right] \\ dp\left[ 1\right] \end{cases} $$
   result就是在以上这2种情况选一个，则是$$result=Max(dp[0]+dp[2],dp[1])$$
4. 当有4家时，我们就可以总结出一个规律，抢这4家最多的钱：
   $$result= \begin{cases}dp\left[ 0\right] +dp\left[ 2\right] \\ dp\left[ 1\right] +num\left[ 3\right]\end{cases} $$
   $$dp[3]=Max(dp[0]+dp[2],dp[1]+num[3])$$

那么当有N家时，我们则可以表示为:
$$result=Max(dp[N-1],dp[N-2])$$
所有最后的代码为：

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