Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# CHOCOLATE DILEMMA

Last Updated on March 28, 2022 by Ria Pathak

### CONCEPTS USED:

Dynamic programming

Hard

### PROBLEM STATEMENT(SIMPLIFIED):

Arnab can take one candy from each row of candies but with the restrictions imposed:

1. There are 3 sections in each row;
2. If he takes candy from jth section in the ith row,then in (i+1)th row ,he can’t choose candy from the same section i.e. jth section.

See original problem statement here

#### For Example :

``````6 6
1 3 5 2 4 6
6 4 5 1 3 2
1 3 5 2 4 6
6 4 5 1 3 2
6 4 5 1 3 2
1 3 5 2 4 6

Arnab selects sweets
row 1: 6
row 2: 6
row 3: 6
row 4: 6
row 5: 5
row 6: 6
sum =35``````

### OBSERVATION:

To get the maximum sum of sweetness values,he must select sweets with maximum sweetness value from each section keeping in mind the constraints mentioned.

Also,you could observe that of all the values of each section ,only the maximum one is relevant.
For example:

``````n=3,m=6;
1 3 5 2 4 6
6 4 5 1 3 2
1 3 5 2 4 6

For the first row,The relevant values for each section are:
section 1: max(1,3) i.e. 3
section 2: max(5,2) i.e. 5
section 3: max(4,6) i.e. 6``````

### SOLVING APPROACH:

This question has a simple and elegant dynamic programming approach.

Let’s define a funtion sweetness_r(i,s) , where i denotes the row which we are currently on and s denotes the section. It is clearly mentioned in the question that we have only 3 sections.Therefore,

sweetness_r(i,0)=a[i][0]+max(sweetness_r(i,1),sweetness_r(i,2));

sweetness_r(i,1)=a[i][1]+max(sweetness_r(i,0),sweetness_r(i,2));

sweetness_r(i,2)=a[i][0]+max(sweetness_r(i,1),sweetness_r(i,0));

Then print the maximum of sweetness_r(n,0),sweetness_r(n,1) and sweetness_r(n,2) ,where n is the number of rows.

### SOLUTIONS:

``` #include <stdio.h>
int max(int x,int y)
{
if(x>y)
return x;
return y;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int a[n][3];
for(int i=0;i<n;i++)
{
for(int j=0;j<3;j++)
{int mx=0;
for(int c=0;c<m/3;c++)
{int x;
scanf("%d",&x);
mx=mx>x?mx:x;
}
a[i][j]=mx;    }
}
int dp[n][3];
dp[0][0]=a[0][0],dp[0][1]=a[0][1],dp[0][2]=a[0][2];
for(int i=1;i<n;i++)
{
for(int j=0;j<3;j++)
{
if(j==0)
dp[i][j]=a[i][j]+max(dp[i-1][1],dp[i-1][2]);
if(j==1)
dp[i][j]=a[i][j]+max(dp[i-1][2],dp[i-1][0]);
if(j==2)
dp[i][j]=a[i][j]+max(dp[i-1][0],dp[i-1][1]);

}
}
printf("%d",max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2])));
return 0;
}#include <stdio.h>

int main(void) {
return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;

int main()
{
int n,m;
cin>>n>>m;
int a[n][3];
for(int i=0;i<n;i++)
{
for(int j=0;j<3;j++)
{int mx=0;
for(int c=0;c<m/3;c++)
{int x;
cin>>x;
mx=max(mx,x);
}
a[i][j]=mx;    }
}
int dp[n][3];
dp[0][0]=a[0][0],dp[0][1]=a[0][1],dp[0][2]=a[0][2];
for(int i=1;i<n;i++)
{
for(int j=0;j<3;j++)
{
if(j==0)
dp[i][j]=a[i][j]+max(dp[i-1][1],dp[i-1][2]);
if(j==1)
dp[i][j]=a[i][j]+max(dp[i-1][2],dp[i-1][0]);
if(j==2)
dp[i][j]=a[i][j]+max(dp[i-1][0],dp[i-1][1]);

}
}
cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
return 0;
}
```
``` import java.util.*;

class solution{
public static void main (String[] args) {

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();
int m=sc.nextInt();

int a[][]=new int[n][3];
for(int i=0;i<n;i++)
{
for(int j=0;j<3;j++)
{
int mx=0;
for(int c=0;c<m/3;c++)
{
int x=sc.nextInt();
mx=Math.max(mx,x);
}
a[i][j]=mx;
}
}
int dp[][]=new int[n][3];
dp[0][0]=a[0][0];dp[0][1]=a[0][1];dp[0][2]=a[0][2];
for(int i=1;i<n;i++)
{
for(int j=0;j<3;j++)
{
if(j==0)
dp[i][j]=a[i][j]+Math.max(dp[i-1][1],dp[i-1][2]);
if(j==1)
dp[i][j]=a[i][j]+Math.max(dp[i-1][2],dp[i-1][0]);
if(j==2)
dp[i][j]=a[i][j]+Math.max(dp[i-1][0],dp[i-1][1]);
}
}
System.out.print(Math.max(dp[n-1][0],Math.max(dp[n-1][1],dp[n-1][2])));
}
}
```

[forminator_quiz id="2190"]

This article tried to discuss 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.