ChunNote
0%

leetCode-213:House Robber II

发表于 分类于

问题描述

给定一个首尾相连的环形数组，表示每个房间的金钱。有一个小偷要从这些房间中将金钱偷走，但是不能偷相邻的两个房间。问小偷能偷走的最大金钱数。题目链接：**点我**

样例输入输出

输入：[2,3,2]

输出：3

说明：小偷偷编号为 1（金钱为 3）的房间，总价值为 3。不能偷编号 0（金钱为2）和编号 2 （金钱为 2）的房间，因为这两个房间是相邻的

输入：[1,2,3,1]

输出：4

说明：小偷偷编号 0（金钱为1）和编号 2 （金钱为 3）的房间，总价值为 4

问题解法

此题跟 LeetCode-198 类似，只不过多了个条件，数组是首尾相连的。所以可以基于 LeetCode-198 的基础，分别作出两种假设，第一种是第一个房间不偷，那最后一个房间就可以偷，此时可以用 LeetCode-198 的解法求出小偷能偷到的最大价值。第二种是第一个房间偷，那最后一个房间不偷，此时同样用 LeetCode-198 的解法求出小偷能偷到的最大价值。将这两种方式下的值进行比较，返回其最大值，就是本题的解。代码如下：

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
30
31
32
33
34
35
36
37
38
39
40
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[] dp = new int[nums.length];
        dp[0] = 0;
        dp[1] = nums[1];
        for (int i = 2; i < nums.length; i++)
        {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        // 第一个偷
        int[] dp2 = new int[nums.length];
        dp2[0] = nums[0];
        dp2[1] = nums[0];
        for (int i = 2; i < nums.length - 1; i++)
        {
            dp2[i] = Math.max(dp2[i - 2] + nums[i], dp2[i - 1]);
        }

        return Math.max(dp[nums.length - 1], dp2[nums.length - 2]);
    }
}