Problem

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.

Example
Given [3, 8, 4], return 8.

思路

• 为什么不是坐标型DP?

  • 假设是坐标型dp

    • 套用模板, 从起点到达第n个点所获得的最大收益

    • 发现很难有O(1) 的转, 我们抢了第n个bank, 那么前一个抢的bank是谁呢?

    • 也就是dp[n] 从前面那个状态转移过来. 需要用O(n) 来枚举上一个bank在哪里

    • 于是我们考虑换状态，

    • dp[n][0]表示前n个bank我们强制选第n个bank所获得的最大收益，

    • dp[n][1]表示前n个bank我们强制“不”选第n个bank所获得的最大收益，

    • 这样很自然的得到了转移方程：dp[n][0] = dp[n - 1][1] + bank[n] //如果最大值第n个银行肯定选中，那么由于相邻bank不能同时选，所以最大收益等于第n-1肯定不选时候的收益加上抢第N个银行的收益

    • dp[n][1] = max(dp[n][0], dp[n][1]) //如果第n个银行肯定不选，那么第n-1个银行可能选也可能不选，取最大值

      我们发现这样设计状态后可以不重不漏的覆盖所有情况，并且转移也是O（n）的

• 正确思路

  • dp[n]表示前n个Bank的最大收益，那么枚举最后一个银行抢或者不抢，取最大值

  • dp[n] = max(dp[n - 1], //不抢第n个银行，那么最大值显然就是抢前n-1个银行的最大值

                     dp\[n - 2\] + bank\[n\]               //抢第n个银行，那么第n-1个银行肯定不能抢了，所以再加上抢前n-2个银行的最大值  
             \)
    

    public long houseRobber(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }

        long[] dp = new long[A.length + 1];
        dp[0] = 0;
        dp[1] = A[0];

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

        return dp[A.length];
    }

滚动数组优化

    public long houseRobber(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }

        long[] dp = new long[3];
        dp[0] = 0;
        dp[1] = A[0];

        for (int i = 2; i <= A.length; i++) {
            dp[i % 3] = Math.max(dp[(i - 1) % 3], dp[(i - 2) % 3] + A[i - 1]);
        }

        return dp[A.length % 3];
    }