# Java O(n) DP solution with 13 lines clean code.

• `````` public int rob(int[] num) {
int n = num.length;
if (n < 2)
return n == 0 ? 0 : num[0];
int[] cache = new int[n];
cache[0] = num[0];
cache[1] = num[0] > num[1] ? num[0] : num[1];
for (int i = 2; i < n; i++) {
cache[i] = cache[i - 2] + num[i];
cache[i] = cache[i] > cache[i-1]? cache[i] : cache[i-1];
}
return cache[n - 1];
}``````

• Could anyone explain why it works ?

• ``````public int rob(int[] num) {
if (num == null || num.length == 0) return 0;
int size = num.length;
if (size == 1) return num[0];
int[] res = new int[size+1];
res[size-1] = num[size-1];
for (int i = size-2; i >= 0; --i)
res[i] = max(num[i] + res[i+2], res[i+1]);
return res[0];
}``````

• It works because it is a basic dynamic programming solution. It is the same as my solution below written in a style you may be familiar with.

• 0 houses return 0.

1 house returns num[0].

2 houses return whichever larger.

For n houses where n>2:

Consider the last house num[n-1]. It is either robbed, or NOT robbed.

If robbed, then amount of money is (total of n-2 houses) + num[n-1].

If NOT robbed, then amount of money is (total of n-1 houses).

Return whichever larger.

• ``````public class Solution {
public int rob(int[] num) {
int rob = 0, noRob = 0;
for (int i = 0; i < num.length; i++) {
int temp = noRob;
noRob = Math.max(rob, noRob);
rob = temp + num[i];
}
return Math.max(rob, noRob);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.