Treat for the Cows

Dynamic Programming, Memoization

Originally posted on Aug 26, 2014 in my previous blog.

Problem posted on SPOJ.com

On first look, we may be urged to use a greedy approach, i.e., always take the lesser value ‘treat’ among the two end ‘treats’. Well, the greedy approach is wrong. Figure it out! (Hint: Check for the testcase [11, 2, 11, 10])

How to go about this problem?

Using recursion – Every time we have an array (size: n) of treats, the maximum values that we can obtain is,

max(arr[mini] * day + treat(mini + 1, maxi),
    arr[maxi] * day + treat(mini, maxi - 1))
                  

'day' is the current day, treat is the function that calculates the max value obtainable recursively (initially we call the function, treat(0, n)). mini and maxi values represent that arr[mini – maxi] are the treats that are available. Also note that, we don’t need to worry about passing the current day value each time. We can calculate it as,

current day =  n - maxi + mini
                  

Clearly, we can observe that we are making a lot of redundant computations. The time complexity of this recursive approach is O(2^n). The original problem consists of many overlapping sub problems. Suppose we calculate a particular problem once and store it in memory, we can use it in the future computations if required. create an n * n matrix and initialize all values with -1. When calling the recursive function, check if that particular value has already been updated, if it is not -1, return that value, otherwise calculate that value.

int func(int top, int bottom) {
    if(top > bottom) {
        return 0;
    }

    if(cache[top][bottom] != -1)    {
        return cache[top][bottom];
    }

    int day = n + top - bottom;

    dp = max(func(top + 1,bottom) + day * arr[top],
             func(top, bottom - 1) + day * arr[bottom]);

    return cache[top][bottom] = dp;
}
                  

Happy coding!