**Problem:** You have n houses with certain amount of money stashed in each house. You can not steal any adjacent houses. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can steal.

**Solution:**

This is a simple dynamic programming problem. The key is figure out the recurrence relation in the given problem.

At first glance, it appears that the robber could just rob every other house – in which case, we ask whether he should start with the first house or the second house; this could maximize the number of houses he robs. However, it is possible that neither of these possibilities maximize the amount of money he’d steal (e.g. house 1 and 4 have a million dollars each, and the rest have no money).

The recurrence relation for stealing the maximum amount of money is the following:

dp[i] = Math.max(dp[i-1], dp[i-2]+num[i-1])

public class CrazyForCode { public int steal(int[] num) { if(num==null || num.length==0){ return 0; } int[] dp= new int[num.length+1]; dp[0]=0; dp[1]=num[0]; for(int i=2; i<=num.length;i++){ dp[i] =Math.max(dp[i-1],num[i-1]+dp[i-2]); } return dp[num.length]; } }

**Time Complexity: O(n)**

public class Solution {

public int rob(int[] nums) {

int m1=0;

int m2=0;

if (nums.length == 0) return 0;

if (nums.length == 1) return nums[0];

if (nums.length == 2) return max(nums[0], nums[1]);

m2 = nums[0];

m1 = max(nums[0], nums[1]);

for (int i=2; i n2) return n1;

return n2;

}

}

Should the recurrence relation have num[i] instead of num[i-1] ?

what would be the output for list [1,25,1,1,24] according to your question also acoording to your logic?

49.

Your algorithm is cool, but the first 2 houses were visited! even though their adjacent. line number 6 in the code visits the first house, then the first iteration visits the seconds house. The input I used is { 1, 6, 89, 2, 55, 599, 8, 2, 9, 1, 3 }