198. House Robber (1d to 2d, 1d, fib)

DFS - over time limit

class Solution {
    public int rob(int[] nums) {
        return dfs(nums, 0);
    }
    private int dfs(int[] nums, int i) {
        if (i >= nums.length) {
            return 0;
        }
        int case1 = nums[i] + dfs(nums, i+2); // 第i天偷, i+2 天才能偷
        int case2 = dfs(nums, i+1); // 第i天不偷, i+1天可以偷
        return Math.max(case1, case2);
    }
}

DFS + memo

T: O(n)

S: O(n)

class Solution {
    public int rob(int[] nums) {
        Integer[] memo = new Integer[nums.length+1];
        return dfs(nums, 0, memo);
    }
    private int dfs(int[] nums, int i, Integer[] memo) {
        if (i >= nums.length) {
            return 0;
        }
        if (memo[i] != null) {
            return memo[i];
        }
        int case1 = nums[i] + dfs(nums, i+2, memo);
        int case2 = dfs(nums, i+1, memo);
        memo[i] = Math.max(case1, case2);
        return memo[i];
    }
ja

same

class Solution {
    public int rob(int[] nums) {
        return dp(nums, 0, new Integer[nums.length]);
    }
    private int dp(int[] nums, int start, Integer memo[]) {
        if (start >= nums.length) {
            return 0;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        int result = 0;
        result += Math.max(nums[start] + dp(nums, start+2, memo), dp(nums, start+1, memo));
        return memo[start] = result;
    }
}

/*
[1,2,3,1]
 x
   x

max(
 nums[i] + dp(i+2) // rob i
 dp(i+1) // not rob i
)

r.  x. i = 0  
/\  /\ 
x   r x  i = 1
/   / /\
r  x  r x i = 2. -> duplicate sub problems

[1,2,3,1]
 r x x r
 x r x r. -> duplicate sub 

before memo: O(2^n), choose or not choose
after memo: O(2n)

*/

dp

注意 限制是不能連續偷

子問題
狀態定義
dp 方程

0~i 可以偷的房子, dp[i] 能偷到的最大金額

=> dp[i], 表示能偷的 max value
=> dp[i] = dp[i-1] + ??? or what?

for (0~n-1)

dp[i] = dp[i-1] + nums[i]   => 可以嗎？  => dp[i-1] 的結果＋搶第i個房子（num[i])

但其實 dp[i-1] 不確定會不會去偷, 所以...
爾且如果偷了 dp[i-1], 就不會偷 nums[i]
所以要多加信息, 到底有沒有偷, 所以多加 "一維"

多加一維後

dp[i][0,1] => 0 不偷, 1偷

第 i 天不偷, 所以 i-1 天可以 偷, 也可以 不偷, 兩者選一個大的
a[i][0] = Max(a[i-1][0], a[i-1][1])

第i天偷, 所以 i-1 天不能偷, 然後第 i 天必偷（所以把 nums[i]算上
a[i][1] = Max(a[i-1][0], 0) + nums[i]

so 開始來寫程式, 初始值
a[0][0] = 0;       // 第一間房子不偷
a[0][1] = nums[0]; // 第一間房子要偷


然後因為題目有說是非負整數
所以 

Max(a[i-1][0], 0) => a[i-1][0]
=>
a[i][1] = a[i-1][0] + nums[i]

最後可以寫出下面的代碼！ 

注意最後回傳
return Math.max(dp[n-1][0], dp[n-1][1]);

time: O(n)

space: O(2n)

class Solution {
    public int rob(int[] nums) {
        // add one more dim, 0: not steal, 1: steal
        // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1])
        // dp[i][1] = dp[i-1][0] + nums[i]
        int n = nums.length;
        int dp[][] = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        return Math.max(dp[n-1][0], dp[n-1][1]);
    }
}

更優化的方式, top down

不用二維的話呢？ 


第i個房子 可偷 或 不偷

dp 變成
dp[i] = max(dp[i-1] 偷 , dp[i-2]偷 + 第i間必偷)
=>
dp[i] = max(dp[i-1] , dp[i-2] + nums[i])


ps.
dp[i-3], dp[i-4]... 不用考慮嗎？ 不用！
dp[i-2] 肯定包含且大於 dp[i-3], dp[i-4]...

like dp[i] = ...dp[i-1], dp[i] 一定是大於 dp[i-1] 對吧？

time: O(n)

space: O(n)

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
        }
        return dp[nums.length-1];
    },
}

button up

非常精簡, 只是空間要多 2

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length+2]; // needs more space for first

        for (int i = nums.length - 1; i >= 0; i--) {
            dp[i] = Math.max(dp[i+1], nums[i] + dp[i+2]);
        }
        return dp[0];
    }

}

更優化

最後, 既然都只剩 dp[i-1] 和 dp[i-2], 是不是可以像 fib 一樣, 用兩個變數來存？

time: O(n)

space: O(1)

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int prevMax = 0;
        int currMax = 0;
        for (int num : nums) {
            int temp = currMax;
            currMax = Math.max(prevMax + num, currMax);
            prevMax = temp;
        }
        return currMax;
    }
}

這樣寫好像更簡單哈...

為了只用變數, 再計算完 dpi (最新的答案後

我們要把 dpi 保留到下一 round, 還有 dpi1 保留, dpi2 可以丟棄

保留 dpi1, dpi

so dpi2 = dpi1

dpi1 = dpi

class Solution {
    pub lic int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int dpi2 = 0;
        int dpi1 = 0;
        int dpi = 0;
        
        for (int i = nums.length - 1; i >= 0; i--) {
            dpi = Math.max(dpi1, nums[i] + dpi2);
            dpi2 = dpi1;
            dpi1 = dpi;
        }
        return dpi;
    }
}

```java
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (nums.length == 1) {
            return nums[0];
        }
        int prevMax = nums[0];
        int currentMax = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            int max = Math.max(prevMax + nums[i], currentMax);
            prevMax = currentMax;
            currentMax = max;
        }
        return currentMax;
    }
}
```