An Easy DP Problem-1

You are given an array a[] of length N. You have to output P such that

p=summation of some array elements. An condition must be hold that is
if you choose the i-th element of the array, then you mustn’t choose the i+1 and i-1 th element. That is you choose the i-th element, then you must not choose the neighbor element of the array.

Sample Input:
7
1 7 2 9 4 6 13
10
1 2 3 4 5 1 2 3 4 5
Sample Output:
29
17

Code:

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int a[100];
int dp[100];
int n;
int f(int pos)
{
    if(dp[pos]) return dp[pos];
    if(pos==n-1) return dp[pos]=a[n-1];
    if(pos>n-1) return dp[pos]=0;
    int p1=a[pos]+f(pos+2); //pos-th nibo
    int p2=f(pos+1);        //pos-th nibo na
    return dp[pos]=max(p1,p2);
}

int main()
{
    int i,j,k,m,d;
    while(cin>>n)
    {
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
            cin>>a[i];
        cout<<f(0)<<endl;
    }
    return 0;
}

Now if an condition is added, that is, first element is neighbor to last element, then, an state is also added which is

int f(int pos,bool first)
pos=position of the array element.
first= 1, if first element is taken
0, if first element is not taken

Code:

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int a[100];
int dp[100][100];
int n;
int f(int pos,bool first)
{
    if(dp[pos][first]) return dp[pos][first];
    if(pos==n-1&&first==0) return dp[pos][first]=a[n-1];
    if(pos==n-1&&first==1) return dp[pos][first]=0;
    if(pos>n-1) return dp[pos][first]=0;
    int p1,p2;
    if(pos==0)
    {
        p1=a[pos]+f(pos+2,1);
        p2=f(pos+1,0);
    }
    else
    {
        if(first==0)
        {
            p1=a[pos]+f(pos+2,0);
            p2=f(pos+1,0);
        }
        else
        {
            p1=a[pos]+f(pos+2,1);
            p2=f(pos+1,1);
        }
    }
    return dp[pos][first]=max(p1,p2);
}
int main()
{
    int i,j,k,m,d;
    while(cin>>n)
    {
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
            cin>>a[i];
        cout<<f(0,0)<<endl;
    }
    return 0;
}
Advertisements
About

ACM Competitive Programmer

Tagged with:
Posted in Dynamic Programming
One comment on “An Easy DP Problem-1
  1. Kaiser says:

    Please give us more instruction & techniques about DP programming.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: