House Robber

Question

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution

非常經典的 DP 題目，但我第二次寫還是不會。基本上就用九章教的分析法來做：

1. State: dp[i] 表示前 i 間房子能搶到的最大金額
2. function: dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]) 因為用前 i 間，所以 index 要減一。可以先縮小到用長度為三的 array 來想，假如是 [2,0,3]，你要看 dp[3]，所以要拿 dp[2] 的結果跟 dp[1] + array[2] 來比較。可以想成因為要去搶 array[2]，所以只能搭配 dp[1]，如果不去搶 array[2]，那就可以拿 dp[2]
3. initialize: dp[0] = 0, dp[1] = nums[0]
4. 求 dp[n] -> 所以初始 array 的長度要是 int[] dp = new int[nums.length + 1]

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

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

        return dp[nums.length];
    }