# Ac solution code

• Special thanks to tusizi

The basic idea is based on DP, while DFS method will take O(n!) runtime approximately.

Solution1. DP - O(n) runtime; O(1) space

``````public int rob(int[] nums) {
//prevNo : we don't rob the previous house
//prevYes: we rob the previous house
int prevYes = 0, prevNo = 0;
for (int i : nums) {
int tmp = prevYes;
prevYes = prevNo + i;
prevNo = Math.max(tmp, prevNo);
}
return Math.max(prevNo, prevYes);
}
``````

Solution2. DP - O(n) runtime; O(n) space

``````public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int dp[][] = new int[nums.length][2];// dp[i][0]: we don't rob house i; dp[i][1]: we rob house i
dp[0][0] = 0;// Initialize house 0
dp[0][1] = nums[0];

for (int i = 1; i < nums.length; 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[nums.length-1][0], dp[nums.length-1][1]);
}
``````

Solution3. DFS - O(n!) runtime - TLE (Only for reference)

DP is generally retrieved from DFS solution, while this DFS solution is the origin of DP idea. Gonna optimize this solution with memorization later.

``````int max = 0;
public int rob(int[] nums) {
DFS(nums, new boolean[nums.length], 0, 0);
return max;
}
void DFS(int[] nums, boolean[] visited, int start, int curSum) {
for (int i = start; i < nums.length; i++) {
if (!visited[i]) {
visited[i] = true;
max = Math.max(max, curSum + nums[i]);
DFS(nums, visited, i + 2, curSum + nums[i]);
visited[i] = false;
}
}
}
``````

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