House Robber

只能搶不相鄰的

我們可以直接寫出來想轉移方程

[3, 8, 4]

index = 0 : 只有 3

index = 1 : 如果搶這間，那麼兩邊不能搶，為 8

index = 2 : 如果這間要搶則不能搶左邊的，但可以搶第一間，把自己+第一間跟第二間的比

這樣公式就出來了!!!

f[i] = Math.max(f[i] + A[i-2], f[i-1])

可是這樣寫的時候去 loop 迴圈會相當麻煩，要去判斷 i-2 >= 0 , 倒不如可以直接多加一個 f[0] 元素，

CODE就很好看了

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

    long f[] = new long[A.length+1];
    f[0] = 0;
    f[1] = A[0];
    for (int i=2; i<=A.length; i++) {
        f[i] = Math.max(A[i-1] + f[i-2], f[i-1]);
    }
    return f[A.length];
}