198. House Robber

阳光穿透心脏的1/2处 2022-08-21 11:41 139阅读 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.

你是一个专业的小偷准备沿街偷窃，这条街道上的房子里都有一些钱财。但是你要注意不能偷相邻的两幢房屋，因为所有相邻的房屋都用报警器连接，一旦两栋房屋同时被盗就会报警引来警察。给定一个数组表示每栋房屋里的钱财，求最多能偷多少钱。

分析：

这道题实际上就是求一个数组中所有不相邻元素的和的最大值（称它为Rob值），首先想到的是用递归：要得到下标从0~n-1的Rob值，可以先计算2~n-1的Rob值和3~n-1的Rob值，则Rob\[2...n-1\]+nums\[0\] 和Rob\[3,n-1\]+nums\[1\]中大的那个就是0~n-1的Rob值。基于此，实现代码如下：

public class Solution {
        public int rob(int[] nums) {
            return Func(nums,0,nums.length-1);
        }
        
        private int Func(int[] nums,int i,int j){
            if(i > j)
                return 0;
            if(i == j)
                return nums[i];
            if(i == j - 1)
                return nums[i] > nums[j] ? nums[i] : nums[j];
            int plan1 = nums[i] + Func(nums,i+2,j);
            int plan2 = nums[i+1] + Func(nums,i+3,j);
            return plan1 > plan2 ? plan1 : plan2;
        }
    }

但是，submit后会发现超时，原因是有些Rob值重复计算了。我们可以采用动态规划的思想，将已经求得的Rob值存到一个数组里，从而避免重复计算。代码如下：

public class Solution {
        public int rob(int[] nums) {
            if(nums.length == 0){
    			return 0;
    		}
    		int[][] res = new int[nums.length+3][nums.length];
    		int[][] flag = new int[nums.length+3][nums.length];
            return Func(res,flag,nums,0,nums.length-1);
        }
        
        private int Func(int[][] res,int[][] flag,int[] nums,int i,int j){
            if(i > j){
            	res[i][j] = 0;
            	flag[i][j] = 1;
                return res[i][j];
            }
            if(i == j){
            	res[i][j] = nums[i];
            	flag[i][j] = 1;
                return res[i][j];
            }
            if(i == j - 1){
            	res[i][j] = nums[i] > nums[j] ? nums[i] : nums[j];
            	flag[i][j] = 1;
                return res[i][j];
            }
            int plan1 = nums[i] + (flag[i+2][j] == 1 ? res[i+2][j] : Func(res,flag,nums,i+2,j));
            int plan2 = nums[i+1] + (flag[i+3][j] == 1 ? res[i+3][j] : Func(res,flag,nums,i+3,j));
            flag[i][j] = 1;
            res[i][j] = plan1 > plan2 ? plan1 : plan2;
            return res[i][j];
        }
    }