LeetCode-198+213

Posted on | In

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，(这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。)影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

这两道题的区别就是多了括号中的条件。

198&213 House Robber 打家劫舍

198示例1

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

198示例2

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

213示例1

1
2
3
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

213示例2

1
2
3
4
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

198思路

我们先看198的思路，这是一个很明显动态规划就可以解决的问题（当然其他方法也有，我这里说动态规划）。
我们用dp[i]来表示从0到i家所能偷到的最大值。当i>=2时，dp[i]=max(dp[i-2]+nums[i],dp[i-1]),其中nums[i]表示第i家的钱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return nums[0];
        } else if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }
        nums[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<nums.length;i++){
            nums[i]=Math.max(nums[i]+nums[i-2],nums[i-1]);
        }
        return nums[nums.length-1];
    }
}

213思路

现在再来看213这道题的话就很简单了，就相当于取两个数的最大值，一个是不偷第n-1家,另一个是不偷第0家。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int rob(int[] nums) {
         // 动态规划，在 198 号问题基础上修改
        int n = nums.length;
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return nums[0];
        } else if (n == 2) {
            return Math.max(nums[0], nums[1]);
        } else {
            // 考虑不抢劫 0 号房间和不抢劫 n-1 号房间的情况
            return Math.max(rob(nums, 0, n-2), rob(nums, 1, n-1));
        }

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