198. House Robber - Medium

題目連結

想法

• 看起來是選中一個初始的位置，然後往後隔一個取一次就好了，但這樣可能會有以下問題:
  • 隔一個取反而取不到大的值
  • 那要隔幾個取?

思路

這題看了DP解答有看懂了，但這種題目到底要怎麼想才能想出答案😂

1. 需要兩個變數，一個是紀錄搶當前的，一個是不搶當前的屋子
2. 每一輪都看到底這間不搶比較高還是搶比較高
3. 最後輸出max值

rob1是搶
rob2是不搶

Code

class Solution {
    public int rob(int[] nums) {
        int rob1 = 0, rob2 = 0;

        for (int i = 0; i < nums.length; ++i) {
            // Determine the max, rob or not rob the current house
            int temp = Math.max(nums[i] + rob1, rob2);
            rob1 = rob2; // 變為不搶，下一輪才能搶
            rob2 = temp; // 下一輪就不搶
        }
        return rob2;
    }
}

2024/04/17

• 只記得分搶與不搶