打家劫舍

布满荆棘的人生 2022-02-26 14:06 182阅读 0赞

**题目描述**

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

给定一个代表每个房屋存放金额的非负整数数组，计算你**在不触动警报装置的情况下**，能够偷窃到的最高金额。

**示例 1:**

输入: [1,2,3,1]
    输出: 4
    解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
         偷窃到的最高金额 = 1 + 3 = 4 。

**示例 2:**

输入: [2,7,9,3,1]
    输出: 12
    解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
         偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解法：  
思路1：可以使用动态规划算法来解题。

//memo[i]代表从左往右遍历，到nums[i]位置，最多能抢劫多少钱
    状态转移方程：memo[i] = Max(nums[i] + memo[i-2], memo[i-1]);
    最优子结构：memo[i-2] 和 memo[i-1]
    边界：memo[0] = nums[0] ， memo[1] =Max(nums[0], nums[1])

代码如下：

/**
    	 * 动态规划法
    	 * 时间复杂度O(n)
    	 * 空间复杂度O(n)
    	 * @param nums
    	 * @return
    	 */
    	public int rob(int[] nums) {
    		if(nums == null || nums.length==0) {
    			return 0;
    		}else if(nums.length==1) {
    			return nums[0];
    		}
    		int len = nums.length;
    		//memo[i]代表从左往右遍历，到nums[i]位置，最多能抢劫多少钱
    		int []memo = new int[len];
    		memo[0] = nums[0];
    		memo[1] = Math.max(nums[0], nums[1]);
    		for(int i=2;i<len;i++) {
    			memo[i] = Math.max(nums[i] + memo[i-2], memo[i-1]);
    		}
    		return memo[len-1];
        }

**继续优化**  
根据状态转移方程（memo\[i\] = Max(nums\[i\] + memo\[i-2\], memo\[i-1\])），计算memo\[i\]的时候，只需要memo\[i-2\]，memo\[i-1\]，所以没必要创建一个memo数组，只需要2个变量即可。**可以把空间复杂度从O(n)降到O(1)**  
代码如下：

public int rob(int[] nums) {
    		if(nums == null || nums.length==0) {
    			return 0;
    		}else if(nums.length==1) {
    			return nums[0];
    		}
    		int len = nums.length;
    		//max代表从左往右遍历，到nums[i]位置，最多能抢劫多少钱
    		int memo_2 = nums[0], memo_1 = Math.max(nums[0], nums[1]) , max=memo_1;
    		for(int i=2;i<len;i++) {
    			max = Math.max(nums[i] + memo_2, memo_1);
    			memo_2 = memo_1;
    			memo_1 = max;
    		}
    		return max;
        }

思路2：看到网友有用记忆化搜索算法，看了下代码没看懂。。。**Mark**一下，日后再研究

/**
         * memo[i] 表示考虑抢劫 nums[i...n] 所能获得的最大收益
         */
        private int[] memo;
    
        /**
         * 方式一：记忆化搜索
         * ① 状态：考虑抢劫 nums[index...num.length） 这个范围内的所有房子
         * ② 状态转移：tryRob(n) = Max{rob(0) + tryRob(2), rob(1) + tryRob(3)... rob(n-3) + tryRob(n-1), rob(n-2), rob(n-1)}
         */
        public int rob(int[] nums) {
            memo = new int[nums.length];
            Arrays.fill(memo, -1);
            return tryRob(nums, 0);
        }
    
        private int tryRob(int[] nums, int index) {
            if (index >= nums.length) {
                return 0;
            }
            // 记忆化搜索可以避免重叠子问题的重复运算
            if (memo[index] != -1) {
                return memo[index];
            }
            // 下面是对状态转移方程的描述
            int res = 0;
            for (int i = index; i < nums.length; i++) {
                res = Math.max(res, nums[i] + tryRob(nums, i + 2));
            }
            memo[index] = res;
            return res;
        }