LeetCode解題紀錄 198. House Robber

House Robber - LeetCode

題目

給定一個數字陣列 nums，nums[i] 代表是一條街上第 i 棟房子裡的錢，你可以從左到右搶走房子裡面的錢，但是連續搶走兩棟緊鄰的房子會觸發警鈴，要求返回最大可搶走的錢

限制

• 1 ≤ nums.length ≤ 100
• 1 ≤ nums[i] ≤ 400

觀察

• 在任意位置最佳解是 1. 搶走目前房子的錢加上相隔上一棟的最佳解，或是不要搶目前房子，而是上一棟房子的最佳解

解法 1 (DP)

• 使用兩個變數來放上一棟以及上上一棟的最佳解

class Solution {
    public int rob(int[] nums) {
        // max2 是上上棟的最佳解, max1 是上一棟的最佳解
        int max2 = 0, max1 = nums[0];
        for(int i=1;i<nums.length;i++) {
            int currMax = Math.max(nums[i]+max2, max1);
            // max2 要更新成 max1 與 max2中最大的，這樣才能讓
            // max2 可以保有過去所有的最大值
            max2 = Math.max(max1, max2);
            max1 = currMax;
        }
        return Math.max(max1, max2);
    }
}

結果

TC：O(n)，SC：O(1)