213. House Robber II - Medium

前往題目

思路

這題的關鍵是如何盡量像House Robber I

1. 分成兩部分，不搶第一間與不搶最後一間，這樣問題就變成House Robber I
2. 各自循環找出最大值

Code

文字解析

class Solution {
    public int rob(int[] nums) {
        // 邊界條件
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int res = 0;
        int rob = nums[1], noRob = 0; // 不搶第一間，那就搶第二間

        // Don't rob first house
        for (int i = 2; i < nums.length; ++i) {
            int robTemp = rob, noRobTemp = noRob;
            // 這間搶，上一間就不能搶，再加上這間搶的錢
            rob = noRobTemp + nums[i];
            // 這間不搶那就看上一間不搶比較多還是搶會比較多
            noRob = Math.max(robTemp, noRobTemp);
        }

        res = Math.max(rob, noRob);

        // 不搶最後一間那就搶第一間
        rob = nums[0];
        noRob = 0;
        // Don't rob last house
        for (int i = 1; i < nums.length - 1; ++i) {
            int robTemp = rob, noRobTemp = noRob;
            rob = noRobTemp + nums[i];
            noRob = Math.max(robTemp, noRobTemp);
        }

        res = Math.max(res, Math.max(rob, noRob));
        return res;
    }
}