searching for dynamic programming solution

Question

Problem : There is a stack consisting of N bricks. You and your friend decide to play a game using this stack. In this game, one can alternatively remove 1/2/3 bricks from the top and the numbers on the bricks removed by the player is added to his score. You have to play in such a way that you obtain maximum possible score while it is given that your friend will also play optimally and you make the first move.

Input Format First line will contain an integer T i.e. number of test cases. There will be two lines corresponding to each test case, first line will contain a number N i.e. number of element in stack and next line will contain N numbers i.e. numbers written on bricks from top to bottom.

Output Format For each test case, print a single line containing your maximum score. I have tried with recursion but didn't work

int recurse(int length, int sequence[5], int i) {
    if(length - i < 3) {
       int sum = 0;
       for(i; i < length; i++) sum += sequence[i];
       return sum;
    } else {
        int sum1 = 0;
        int sum2 = 0;
        int sum3 = 0;
        sum1 += recurse(length, sequence, i+1);
        sum2 += recurse(length, sequence, i+2);
        sum3 += recurse(length, sequence, i+3);
        return max(max(sum1,sum2),sum3);
    }
}



int main() {
    int sequence[] = {0, 0, 9, 1, 999};
    int length = 5;
    cout << recurse(length, sequence, 0);
    return 0;
}

Answer 1

My approach to solving this problem was as follows:

Both players play optimally.

So, the solution is to be built in a manner that need not take the player into account. This is because both players are going to pick the best choice available to them for any given state of the stack of bricks.

The base cases:

Either player, when left with the last one/two/three bricks, will choose to remove all bricks.

For the sake of convenience, let's assume that the array is actually in reverse order (i.e. a[0] is the value of the bottom-most brick in the stack) (This can easily be incorporated by performing a reverse operation on the array.)

So, the base cases are:

# Base Cases
dp[0] = a[0]
dp[1] = a[0]+a[1]
dp[2] = a[0]+a[1]+a[2]

Building the final solution:

Now, in each iteration, a player has 3 choices.

1. pick brick (i), or,
2. pick brick (i and i-1) , or,
3. pick brick (i,i-1 and i-2)

If the player opted for choice 1, the following would result:

• player secures a[i] points from the brick (i) (+a[i])
• will not be able to procure the points on the bricks removed by the opponent. This value is stored in dp[i-1] (which the opponent will end up scoring by virtue of this choice made by the player).
• will surely procure the points on the bricks not removed by the opponent. (+ Sum of all the bricks up until brick (i-1) not removed by opponent )

A prefix array to store the partial sums of points of bricks can be computed as follows:

# build prefix sum array
pre = [a[0]]
for i in range(1,n):
    pre.append(pre[-1]+a[i])

And, now, if player opted for choice 1, the score would be:

ans1 = a[i] + (pre[i-1] - dp[i-1]) 

Similarly, for choices 2 and 3. So, we get:

ans1 = a[i]+ (pre[i-1] - dp[i-1])   # if we pick only ith brick
ans2 = a[i]+a[i-1]+(pre[i-2] - dp[i-2]) # pick 2 bricks
ans3 = a[i]+a[i-1]+a[i-2]+(pre[i-3] - dp[i-3])    # pick 3 bricks

Now, each player wants to maximize this value. So, in each iteration, we pick the maximum among ans1, ans2 and ans3. dp[i] = max(ans1, ans2, ans3)

Now, all we have to do is to iterate from 3 through to n-1 to get the required solution.

Here is the final snippet in python:

a = map(int, raw_input().split())

a.reverse()                 # so that a[0] is bottom brick of stack
dp = [0 for x1 in xrange(n)]
dp[0] = a[0]
dp[1] = a[0]+a[1]
dp[2] = a[0]+a[1]+a[2]

# build prefix sum array
pre = [a[0]]
for i in range(1,n):
    pre.append(pre[-1]+a[i])

for i in xrange(3,n):
    # We can pick brick i, (i,i-1) or (i,i-1,i-2)
    ans1 = a[i]+ (pre[i-1] - dp[i-1])   # if we pick only ith brick
    ans2 = a[i]+a[i-1]+(pre[i-2] - dp[i-2]) # pick 2
    ans3 = a[i]+a[i-1]+a[i-2]+(pre[i-3] - dp[i-3])    #pick 3

    # both players maximise this value. Doesn't matter who is playing
    dp[i] = max(ans1, ans2, ans3)
print dp[n-1] 

Answer 2

At a first sight your code seems totally wrong for a couple of reasons:

1. The player is not taken into account. You taking a brick or your friend taking a brick is not the same (you've to maximize your score, the total is of course always the total of the score on the bricks).

2. Looks just some form of recursion with no memoization and that approach will obviously explode to exponential computing time (you're using the "brute force" approach, enumerating all possible games).

A dynamic programming approach is clearly possible because the best possible continuation of a game doesn't depend on how you reached a certain state. For the state of the game you'd need

• Who's next to play (you or your friend)
• How many bricks are left on the stack

With these two input you can compute how much you can collect from that point to the end of the game. To do this there are two cases

1. It's your turn

You need to try to collect 1, 2 or 3 and call recursively on the next game state where the opponent will have to choose. Of the three cases you keep what is the highest result

2. It's opponent turn

You need to simulate collection of 1, 2 or 3 bricks and call recursively on next game state where you'll have to choose. Of the three cases you keep what is the lowest result (because the opponent is trying to maximize his/her result, not yours).

At the very begin of the function you just need to check if the same game state has been processed before, and when returning from a computation you need to store the result. Thanks to this lookup/memorization the search time will not be exponential, but linear in the number of distinct game states (just 2*N where N is the number of bricks).

In Python:

memory = {}
bricks = [0, 0, 9, 1, 999]

def maxResult(my_turn, index):
    key = (my_turn, index)
    if key in memory:
        return memory[key]
    if index == len(bricks):
        result = 0
    elif my_turn:
        result = None
        s = 0
        for i in range(index, min(index+3, len(bricks))):
            s += bricks[i]
            x = s + maxResult(False, i+1)
            if result is None or x > result:
                result = x
    else:
        result = None
        for i in range(index, min(index+3, len(bricks))):
            x = maxResult(True, i+1)
            if result is None or x < result:
                result = x
    memory[key] = result
    return result

print maxResult(True, 0)

Answer 3

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

        public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int noTest=sc.nextInt();
        for(int i=0; i<noTest; i++){
            int noBrick=sc.nextInt();
            ArrayList<Integer> arr=new ArrayList<Integer>();
            for (int j=0; j<noBrick; j++){
                arr.add(sc.nextInt());
            }
            long sum[]= new long[noBrick];
            sum[noBrick-1]= arr.get(noBrick-1); 
            for (int j=noBrick-2; j>=0; j--){
                sum[j]= sum[j+1]+ arr.get(j); 
            }
            long[] max=new long[noBrick];
            if(noBrick>=1)
            max[noBrick-1]=arr.get(noBrick-1);
            if(noBrick>=2)
            max[noBrick-2]=(int)Math.max(arr.get(noBrick-2),max[noBrick-1]+arr.get(noBrick-2));
            if(noBrick>=3)
            max[noBrick-3]=(int)Math.max(arr.get(noBrick-3),max[noBrick-2]+arr.get(noBrick-3));
            if(noBrick>=4){
                for (int j=noBrick-4; j>=0; j--){
                    long opt1= arr.get(j)+sum[j+1]-max[j+1];
                    long opt2= arr.get(j)+arr.get(j+1)+sum[j+2]-max[j+2];
                    long opt3= arr.get(j)+arr.get(j+1)+arr.get(j+2)+sum[j+3]-max[j+3];
                    max[j]= (long)Math.max(opt1,Math.max(opt2,opt3));
                }
            }
            long cost= max[0]; 
            System.out.println(cost);
        }

    }
}

I tried this using Java, seems to work alright.

Answer 4

here a better solution that i found on the internet without recursion.

#include <iostream>
#include <fstream>
#include <algorithm>
#define MAXINDEX 10001
using namespace std;

long long maxResult(int a[MAXINDEX], int LENGTH){
    long long prefixSum [MAXINDEX] = {0};
    prefixSum[0] = a[0];
    for(int i = 1; i < LENGTH; i++){
        prefixSum[i] += prefixSum[i-1] + a[i];
    }

    long long dp[MAXINDEX] = {0};
    dp[0] = a[0];
    dp[1] = dp[0] + a[1];
    dp[2] = dp[1] + a[2];
    for(int k = 3; k < LENGTH; k++){
        long long x = prefixSum[k-1] + a[k] - dp[k-1];
        long long y = prefixSum[k-2] + a[k] + a[k-1] - dp[k-2];
        long long z = prefixSum[k-3] + a[k] + a[k-1] + a[k-2] - dp[k-3];
        dp[k] = max(x,max(y,z));
    }
    return dp[LENGTH-1];
}

using namespace std;

int main(){
    int cases;
    int bricks[MAXINDEX];
    ifstream fin("test.in");
    fin >> cases;
    for (int i = 0; i < cases; i++){
        long n;
        fin >> n;
        for(int j = 0; j < n; j++) fin >> bricks[j];
        reverse(bricks, bricks+n);
        cout << maxResult(bricks, n)<< endl;
    }
    return 0;
}