Question: Given a list of non-negative integers representing the value of each cell, determine the maximum amount of value you can get keeping in mind that you can’t use adjacent cells together.

Now in this question, at first you might think of a greedy solution to take the largest element one by one if none of its neighbours is taken yet. But the problem with this approach is that it does not ensures a global optimal solution.

For instance, take this array

Input: [1,4,6,5]

If we try to apply greedy approach here
We will take 6 from the array and after that our only option left is 1 so the final answer we get is 1+6=7, which we can clearly see is not the best answer because we can get 4+5=9.

Let’s try to think if we can solve this problem using Dynamic Programming.

For this we need two things, first a DP state and second is base cases.

Let’s take

  1. DP[i] =  maximum amount of value we can get till position i.
  2. A[i] = value of ith cell.

Base case:

  1. DP[0]=0 because we haven’t used any cell yet.
  2. DP[1]=value of first cell.

To calculate DP[i], we have two choices:

  1. Choose current index: In this case we can’t use the adjacent index i.e., (i-1)th index so the answer will be (DP[i-2]+A[i])
  2. Leave the current index: In this case our answer will be same as DP[i-1].
To get optimal solution, we will
take maximum of the two choices i.e., DP[i]=max(DP[i-1],DP[i-2]+A[i]).
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<int> a(n+1),dp(n+1,0);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	dp[0]=0;
	dp[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		dp[i]=max(dp[i-1],dp[i-2]+a[i]);
	}
	cout<<dp[n]<<endl;
	return 0;
}

Input:

5

[2 ,8, 9, 8, 1]

Output:

16

That’s all I have and thanks a lot for reading 😉 . Please let me know if any corrections/suggestions. Please do share and comments if you like the post. Thanks in advance…

Thanks Shiva Gupta for helping us to grow day by day. Shiva is expert in Data Structure and loves to solve competitive problems.


0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert