213. House Robber II (Medium)

1.問題

• 你是位專業的強盜, 計畫搶劫一條街上的房子. 每間房子都存有各自的金額. 所有的房子都被排列到一個圓上. 所以第一間房子也會是最後一間房子.相鄰的房子的保全系統是相連的, 而且若相鄰的房子遭破壞時將會自通知警察

• 給予一個代表每間房子內金額的list, 找出不被報警下可搶得的最大金額

2.想法

• Dynamic programming

  • 迴圈list中的所有店家:

    • 每回合要選擇可以賺最多錢的選項

      • 1.到前前家為止所儲存錢 + 偷這一間的錢

      • 2.到前家為止所儲存錢 + 不偷這一間的錢

  • 由於房子排列成圓形, 因此有兩種情形要考慮:

    • 1.選擇第一間 + 選擇倒數第二間時

    • 2.選擇第二間 + 選擇倒數第一間時

3.程式碼

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() < 2)
        {
            return nums.size() == 0 ? 0 : nums[0];
        }
        return max(robAsLine(nums, 0, nums.size() - 2), robAsLine(nums, 1, nums.size() - 1));
    }
private:
    int robAsLine(vector<int>& nums, int start, int end) {
        //Retuen if the size of the list smaller than 2
        if (nums.size() < 2)
        {
            return nums.size() == 0 ? 0 : nums[0];
        }
        int lastTime = 0, secondLastTime = 0;
        for (int l = start; l < end + 1; l++)
        {
            int recordLastTime = lastTime, recordSecondLastTime = secondLastTime;
            secondLastTime = recordLastTime + nums[l];
            lastTime = max(recordLastTime, recordSecondLastTime);
        }
        return max(lastTime, secondLastTime);
    }
};

4.Performance