Saturday, February 23, 2013

No. 44 - Dynamic Programming on Stolen Values


Problem: There are n houses built in a line, each of which contains some value in it. A thief is going to steal the maximal value in these houses, but he cannot steal in two adjacent houses because the owner of a stolen house will tell his two neighbors on the left and right side. What is the maximal stolen value?

For example, if there are four houses with values {6, 1, 2, 7}, the maximal stolen value is 13 when the first and fourth houses are stolen.

Analysis: A function f(i) is defined to denote the maximal stolen value from the first house to the ith house, and the value contained in the ith house is denoted as vi. When the thief reaches the ith house, he has two choices: to steal or not. Therefore, f(i) can be defined with the following equation:
It would be much more efficient to calculate in bottom-up order than to calculate recursively. It looks like a 1D array with size n is needed, but actually it is only necessary to cache two values for f(i-1) and f(i-2) to calculate f(i).


This algorithm can be implemented with the following C++ code:

int maxStolenValue(const vector<int>& values)
{
    int length = values.size();
    if(length == 0)
        return 0;

    int value1 = values[0];
    if(length == 1)
        return value1;

    int value2 = max<int>(values[0], values[1]);
    if(length == 2)
        return value2;

    int value;
    for(int i = 2; i < length; ++i)
    {
        value = max<int>(value2, value1 + values[i]);
        value1 = value2;
        value2 = value;
    }

    return value;
}

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

6 comments:

  1. It took me a while to understand this. I think a really easy way to explain this, is that if a field's value is greater than both of its neighbors (the combined values of whom you'd lose if you chose), then you choose that field. Thanks for posting this.

    ReplyDelete
  2. It took me a while to understand this. I think a really easy way to explain this, is that if a field's value is greater than both of its neighbors (the combined values of whom you'd lose if you chose), then you choose that field. Thanks for posting this.

    ReplyDelete
  3. Programming is very interesting and creative thing if you do it with love. Your blog code helps a lot to beginners to learn programming from basic to advance level. I really love this blog because I learn a lot from here and this process is still continuing.
    Love from Pro Programmer

    ReplyDelete
  4. My approach with DP

    public static int steal(int[] houses) {
    Map> cache = new HashMap<>();
    return traverseCasas(houses, -2, cache).stream().map(i -> houses[i]).reduce(0, (a, b) -> a + b);
    }

    private static List traverseCasas(int[] houses, int idx, Map> cache) {
    if (cache.containsKey(idx) ) {
    return cache.get(idx);
    }

    if (idx >= houses.length) {
    return new ArrayList<>();
    }

    List close = new ArrayList<>();
    close.addAll(traverseCasas(houses, idx + 2, cache));
    List far = new ArrayList<>();
    far.addAll(traverseCasas(houses, idx + 3, cache));

    int sumClose = close.stream().map(i -> houses[i]).reduce(0, (a, b) -> a + b);
    int sumfar = far.stream().map(i -> houses[i]).reduce(0, (a, b) -> a + b);


    cache.put(idx, sumClose > sumfar ? close : far);
    if (idx >= 0) {
    cache.get(idx).add(idx);
    }
    return cache.get(idx);
    }

    ReplyDelete
  5. What a wonderful post. I would like to say that this post is really very informational post. I really like it. programming assignments help

    ReplyDelete