House Robber | Dynamic Programming

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)

7 Thoughts on “House Robber | Dynamic Programming

  1. 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;
    }
    }

  2. Pranav on November 7, 2016 at 5:39 am said:

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

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

  4. 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 }

  5. Aezraar on July 11, 2018 at 11:18 am said:

    Hi,
    public int findMaximumStolenValueFromHouses(int[] houseValues) {
    int[] maxStolenValues = new int[houseValues.length + 1];
    maxStolenValues[0] = 0;
    maxStolenValues[1] = houseValues[0];
    for (int i = 2; i < houseValues.length; i++) {
    maxStolenValues[i] = Math.max(maxStolenValues[i - 1], maxStolenValues[i - 2] + houseValues[i]);
    }
    return maxStolenValues[houseValues.length - 1];
    }

  6. barkha on August 5, 2019 at 3:24 am said:

    public static int steal(int[] num) {
    if (num == null || num.length == 0) {
    return 0;
    }

    int oddPositionTotal = 0;
    int evenPositionTotal = 0;

    for (int i = 0; i <= num.length-1; i = i+2) {
    if(i+1 <= num.length-1) {
    oddPositionTotal += num[i+1];
    }
    evenPositionTotal += num[i];
    }

    return Math.max(oddPositionTotal, evenPositionTotal);
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation