leetcode 198-打家劫舍

题目

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

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

示例

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

限制

1 <= nums.length <= 100 0 <= nums[i] <= 400

解法一

内容

1、暴力法，深搜，尝试枚举每间房间 偷 or 不偷的收益组合情况 2、时间复杂度：O(N2)。每个子问题的时间复杂度分别为{N，N-1，…，1}，等差数列求和。 3、空间复杂度：O(N)。递归开销。

代码（不通过，55/68）

class Solution {
    public int dfs(int[] nums, int index, int sum){
        if(index >= nums.length)
            return 0;
        //根据每个房间选或不选，进行搜索
        return Math.max(dfs(nums, index+1, sum), nums[index]+dfs(nums, index+2, sum));
    }
    public int rob(int[] nums) {
        return dfs(nums, 0, 0);
    }
}

解法二

内容

1、记忆化搜索，在深搜的过程中保存 不同的选择对应的收益，减少重复计算。 2、时间复杂度：O(N)。 3、空间复杂度：O(N)。递归开销。

代码：

class Solution {
    HashMap<Integer, Integer> map;
    public int dfs(int[] nums, int index, int sum){
        if(index >= nums.length)
            return 0;
        //利用先前保存的结果
        if(map.get(index) != null)
            return map.get(index);

        map.put(index, Math.max(dfs(nums, index+1, sum), nums[index]+dfs(nums, index+2, sum)));
        return map.get(index);
    }
    public int rob(int[] nums) {
        map = new HashMap<Integer, Integer>();
        return dfs(nums, 0, 0);
    }
}

解法三

内容

1、二维动态规划，状态定义如下

• dp[i][0] 代表前i间房屋中的最大偷窃收益，且不偷第 i 家。

• dp[i][1] 代表前i间房屋中的最大偷窃收益，且偷第 i 家。

• 状态转移方程1：dp[i][0] = max{dp[i-1][0],dp[i-1][1]}。（如果不偷第 i 家，那么可以选择 偷第 i-1 家，即dp[i-1][1]，也可以选择不偷第 i-1家的，即 dp[i-1][0]）
• 状态转移方程2：dp[i][1] = dp[i-1][0]+nums[i]。(因为偷了第 i 家的，所以不能从前面的状态中不能出现偷第 i-1 家的，所以只有 dp[i-1][0])
• 初始化：dp[0][0] = 0，dp[0][1] = nums[0]。

2、时间复杂度：O(N)。 3、空间复杂度：O(2N)。

代码

class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        if(nums.length == 1)
            return nums[0];
        if(nums.length == 2)
            return Math.max(nums[0], nums[1]);

        int n = nums.length;
        int[][] dp = new int[n][2];
        //二维dp问题
        //dp[i][0] 代表前i间房屋中的最大偷窃收益，且不偷第 i 家
        //dp[i][1] 代表前i间房屋中的最大偷窃收益，且偷第 i 家
        //dp[i][0] = max{dp[i-1][0],dp[i-1][1]}
        //dp[i][1] = dp[i-1][0]+nums[i]
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for(int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        return Math.max(dp[n-1][0], dp[n-1][1]);
    }
}

解法四

内容

1、假设f(k)是代表前k个房间里能够偷窃到的最高金额。

• dp[len+1] 需要借一位，不然没办法表示第一间偷 or 不偷的状态。
• 对f(k)进行初始化，f(0)=0，f(1)=nums[0]，f(2)=max(nums[0]，nums[1])。
• 当k=3时，我们有两种选择，第一种是选择第一间房屋和第三间房屋，第二种是选择第二间房屋，即f(3)=max(f(1)+nums[2]，f(2))。
• 当k>=3时，推导出状态转移方程的一般式：f(k)=max(f(k-2)+nums[k-1]，f(k-1))（在这里解释一下，本来应该是nums[k]的，但是nums数组是从下标为0开始计算的，为了编程方便，就改成了nums[k-1]）

代码

class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        if(nums.length == 1)
            return nums[0];
        if(nums.length == 2)
            return Math.max(nums[0], nums[1]);

        int n = nums.length;
        //一维dp问题
        int[] dp = new int[n+1];
        //dp[i] = max{dp[i-2]+nums[i],dp[i-1]} i >= 2
        dp[1] = nums[0];
        for(int i = 2; i <= n; i++){
            dp[i] = Math.max(dp[i-2]+nums[i-1], dp[i-1]);
        }
        return dp[n];
    }
}