Last Updated on March 31, 2022 by Ria Pathak
CONCEPTS USED:
Dynamic programming
DIFFICULTY LEVEL:
Medium.
PROBLEM STATEMENT(SIMPLIFIED):
After having lost to you again, your friend challenges you yet again for another round of Monopoly.
This time, he changes the rules of the game slightly, hoping that this would throw you off your game and he would finally have his sweet revenge. Your task is to play optimally and win this, again!
The updated rules are as follows :Consider a row of
N notes of values V1,V2…Vn, where N is even. We play a game against an opponent by alternating turns. In each turn, a player performs this operation K times: select either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin.
Determine the maximum possible amount of money we can definitely win if we move first.
For Example :
5 2
2 7 9 4 4
In the first step, you take 2 and 7
Opponent takes 9 and 4.
You take 4 at the end.
So total= 13. SOLVING APPROACH:
Let’s define a function f(st,end) where st is the starting index and end is the ending index available for the player to select coins.
Now try to understand that from the given i and j(starting and ending index) we can easily figure out whose turn it is.
sz=j-i+1; diff=n-sz; diff=diff/k;Now ,if diff%2=0,it’s the turn of first player,else second player plays.
Base case-
if sz i.e. the available range is less than k,then add all the elements in the array.
We have the maximise the sum if it’s the turn of first player and minimise if the it’s the turn of second player.
You are encouraged to implement the above brute force and think of memoization on your own first ,before looking at the solution.
See original problem statement here
The above brute force gives exponential time complexity as several subproblems will be computed repetitively. To overcome this,we use memoization technique.
Refer to the code below:
#include <stdio.h>
#define ll long long
ll dp[101][101];
ll arr[101];
int n,k;
ll max(ll x,ll y)
{
if(x>y)return x;return y;
}
ll min(ll x,ll y)
{
if(x<y)return x;
return y;
}
ll solve(int st,int end){
if(dp[st][end]!=-1)
return dp[st][end];
ll sz=(end-st+1);
ll diff=n-sz;
diff=(diff)/k;
//cout<<st<<" "<<end<<endl;
if(diff%2==0){
if(sz<=k){
ll sum=0;
for(int i=st;i<=end;i++){
sum+=arr[i];
}
return dp[st][end]=sum;
}
else{
ll val1=-1;
for(int i=0;i<=k;i++){
int cnt1=i,cnt2=k-i;
int st1=st,end1=end;
ll sum=0;
while(cnt1){
sum+=arr[st1];
st1++;
--cnt1;
}
while(cnt2){
sum+=arr[end1];
--end1;
--cnt2;
}
val1=max(val1,sum+solve(st1,end1));
}
return dp[st][end]=val1;
}
}
else{
if(sz<=k){
return dp[st][end]=0;
}
else{
ll val2=1000000000000000000;
for(int i=0;i<=k;i++){
int j=k-i;
val2=min(val2,solve(st+i,(end-j)));
}
return dp[st][end]=val2;
}
}
}
int main(){
scanf("%d%d",&n,&k);
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++){
scanf("%lld",&arr[i]);
}
printf("%lld",solve(0,n-1));
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[101][101];
ll arr[101];
int n,k;
ll solve(int st,int end){
if(dp[st][end]!=-1)
return dp[st][end];
ll sz=(end-st+1);
ll diff=n-sz;
diff=(diff)/k;
//cout<<st<<" "<<end<<endl;
if(diff%2==0){
if(sz<=k){
ll sum=0;
for(int i=st;i<=end;i++){
sum+=arr[i];
}
return dp[st][end]=sum;
}
else{
ll val1=INT_MIN;
for(int i=0;i<=k;i++){
int cnt1=i,cnt2=k-i;
int st1=st,end1=end;
ll sum=0;
while(cnt1){
sum+=arr[st1];
st1++;
--cnt1;
}
while(cnt2){
sum+=arr[end1];
--end1;
--cnt2;
}
val1=max(val1,sum+solve(st1,end1));
}
return dp[st][end]=val1;
}
}
else{
if(sz<=k){
return dp[st][end]=0;
}
else{
ll val2=INT_MAX;
for(int i=0;i<=k;i++){
int j=k-i;
val2=min(val2,solve(st+i,(end-j)));
}
return dp[st][end]=val2;
}
}
}
int main(){
cin>>n>>k;
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<solve(0,n-1);
return 0;
}
import java.util.*;
class solution{
static int n, k;
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
long dp[][]=new long[101][101];
long arr[]=new long[101];
n=sc.nextInt();
k=sc.nextInt();
for(int i=0;i<n;i++)
arr[i]=sc.nextLong();
for(int i=0;i<dp.length;i++){
for(int j=0;j<dp[0].length;j++){
dp[i][j]=-1;
}
}
System.out.println(solve(0,n-1,arr,dp));
}
static long solve(int st,int end,long arr[],long dp[][])
{
if(dp[st][end]!=-1)
return dp[st][end];
long sz=(end-st+1);
long diff=n-sz;
diff=(diff)/k; //cout<<st<<" "<<end<<endl;
if(diff%2==0){
if(sz<=k){
long sum=0;
for(int i=st;i<=end;i++){
sum+=arr[i];
}
return dp[st][end]=sum;
}
else{
long val1=Integer.MIN_VALUE;
for(int i=0;i<=k;i++){
int cnt1=i,cnt2=k-i;
int st1=st,end1=end;
long sum=0;
while(cnt1>0){
sum+=arr[st1];
st1++;
--cnt1;
}
while(cnt2>0){
sum+=arr[end1];
--end1;
--cnt2;
}
val1=Math.max(val1,sum+solve(st1,end1,arr,dp));
}
return dp[st][end]=val1;
}
}
else{
if(sz<=k){
return dp[st][end]=0;
}
else{
long val2=Integer.MAX_VALUE;
for(int i=0;i<=k;i++){
int j=k-i;
val2=Math.min(val2,solve(st+i,(end-j),arr,dp));
}
return dp[st][end]=val2;
}
}
}
}
Space complexity: O(n*n)
[forminator_quiz id="2249"]
This article tried to discuss the concept of Dynamic programming. Hope this blog helps you understand and solve the problem. To practice more problems on Dynamic programming you can check out MYCODE | Competitive Programming.