题目描述

房子排成一个圈，不能抢劫相连的房子，求最大值。

样例

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

算法1

DP $O(n)$

分开讨论抢劫house 0 和 不抢劫 house 0 两种情况，皆可以转化为 House Robber I的问题。

C++ 代码

    // 分2种情况: (1) rob house 0, 则不能rob 1和n-1，可rob 2..n-2, 最优为x[0] + rob1(xs, 2, n-2)
    // (2) 不 rob 0，则 1..n-1可以自由rob，rob1(xs, 1, n-1);
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0;
        if(n==1) return nums[0];

        int opt1 = nums[0] + rob1(nums, 2, n-2);
        int opt2 = rob1(nums, 1, n-1);
        return max(opt1, opt2);
    }

    // house i..j 是线性排列的，且首尾不想连，求最大值
    int rob1(vector<int>& xs, int i, int j) {
        if(i>j)  return 0;
        if(i==j) return xs[i];

        int fn_2 = 0, fn_1 = xs[i];
        for(int k=i+1; k<=j; k++) {
            int t = max( xs[k] + fn_2, fn_1);
            fn_2 = fn_1;
            fn_1 = t;
        }

        return fn_1;
    }