leetcode 198题目

给定一个数组（不同权重（钱）的店家），强盗可以抢不相邻的店家，求最大的钱数。

1. 暴力搜索

• 代码

public class HouseRobber {
    public int rob(int[] nums) {
        //return solve(nums.length-1 ,nums);
        return solve(0 ,nums);
    }

    private int solve(int idx, int[] nums) {
        if(idx > nums.length-1){
            return 0;
        }
        return Math.max(solve(idx+1,nums),solve(idx+2,nums) + nums[idx]);
    }
}

solve(int idx, int[] nums):抢下标为idx的店，最大的钱数。
return Math.max(solve(idx+1,nums),solve(idx+2,nums) + nums[idx]);
对于idx的店家只有两种可能：

• 抢idx的话 solve(idx+2,nums) + nums[idx]
• 不抢idx的话 solve(idx+1,nums)

结果：超时！
原因：

• n->(n-2,n-3,n-4) 状态n由前n-2个状态决定 前n-2个状态每个都要算一遍

• n-1->(n-3,n-4,n-5) 状态n-1由前n-3个状态决定 前n-3个状态每个都要算一遍

大量的重复运算，导致时间复杂度剧增，需要存储已经计算过的状态来解决这个问题

2. 改进

    private static int[] res = null;

    public static int rob(int[] nums) {
        res = new int[nums.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = -1 ;
        }
        return solve(0, nums);
    }

    private static int solve(int idx, int[] nums) {
        if (idx > nums.length - 1) {
            return 0;
        }
        if (res[idx] >= 0 ) {
            return res[idx];
        }
        res[idx] = Math.max(solve(idx + 1, nums), solve(idx + 2, nums) + nums[idx]);
        return res[idx];
    }

用res数组来记录已经计算过的状态
if (res[idx] >= 0 ) { return res[idx]; }
计算过的话，直接返回，去除冗余计算。

动态规划

public class HouseRobber {

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length]; //记录抢到某个下标时的最优解
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[dp.length - 1];
    }
}

1. 实质：递归
2. 最优子结构

• 子问题最优决策可以导出原问题的最优决策
• 无后效性：抢了第n家店之后，后面的n-1家店不能抢（影响到了后面的决策）；而这里进入了n-2，跳过了n-1,。

3. 重叠子问题
   • 去冗余
   • 空间换时间