Dynamic Programming

DP Problem #1: Minimum steps to one
        Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.

Example:
        Given coins with values 1, 3, and 5.
        And the sum S is set to be 11.

Solution:

#include

using namespace std;

#define INFINITE 999999

int main()
{
        const int S = 11; // sum to calculate.
        const int N = 3;  // number of coins available.
        int v[N] = {1,3,5}; // face value of all the coins.
        int min[S+1];

        for(int i=0;i<12;i++)
                min[i] = INFINITE; // we havent yet found a solution for this one.

        min[0] = 0; // sum of 0 requires minimum number of 0 coins.

        for(int s=1;s<=S;s++) // start from 1 since we have found a solution for sum = 0.
        {
                for(int n=0;n
                {
                        if(v[n]<=s && min[s]>1+min[s-v[n]])
                        {
                                min[s] = min[s-v[n]]+1;
                        }
                }
        }
        cout << "Coins required for sum[" << S << "] = " << min[S] << endl;
}

Output:
Coins required for sum[11] = 3

DP Problem #2: Maximum number of apples
        A table composed of NxM cells, each having a certain quantity of apples, is given. You start from the upper-left corner. At each step you can go down or right one cell. Find the maximum number of apples you can collect.

Example:
    Consider the table as described in the code

Solution:
#include

int max(int a, int b)
{
        return (a>b)?a:b;
}

int main()
{
        const int N = 10;
        const int M = 10;
        int A[N+1][M+1] = {     {1,2,3,4,5,6,7,8,9,0},
                                {2,4,6,8,0,1,3,5,7,9},
                                {1,1,1,1,1,1,1,1,1,1},
                                {3,5,7,9,2,4,6,7,4,3},
                                {3,3,3,6,4,6,2,3,4,6},
                                {4,9,1,3,1,8,8,1,5,2},
                                {2,1,0,3,9,2,4,3,6,7},
                                {0,0,6,9,8,9,6,1,0,9},
                                {9,4,4,5,1,5,6,6,6,5},
                                {9,8,4,1,0,1,0,1,4,1}};

        int S[N+1][M+1];

        for(int n=0;n<=N;n++)
        {
                for(int m=0;m<=M;m++)
                {
                        S[n][m] = 0;
                        S[n][m] = A[n][m] + max(((m>0)?S[n][m-1]:0),((n>0)?S[n-1][m]:0));
                }
        }

        cout << "Maximum apples collected = " << S[N][M] << endl;
}

Output:
Maximum apples collected = 99 

The path  traversed is 1 - 2 - 4 - 6 - 8 - 1 - 9 - 6 - 3 - 3 - 9 - 8 - 9 - 6 - 6 - 6 - 6 - 5 - 1.

DP Problem #3: Minimum number of coins
    Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.


Example:
    Given coins with values 1, 3, and 5. Find the minimum number of coins for sum 11.


Solution:
#include

using namespace std;

#define INFINITE 999999

int main()
{
        const int S = 11; // sum to calculate.
        const int N = 3;  // number of coins available.
        int v[N] = {1,3,5}; // face value of all the coins.
        int min[S+1];

        for(int i=0;i<12;i++)
                min[i] = INFINITE; // we havent yet found a solution for this one.

        min[0] = 0; // sum of 0 requires minimum number of 0 coins.

        for(int s=1;s<=S;s++) // start from 1 since we have found a solution for sum = 0.
        {
                for(int n=0;n
                {
                        if(v[n]<=s && min[s]>1+min[s-v[n]])
                        {
                                min[s] = min[s-v[n]]+1;
                        }
                }
        }
        cout << "Coins required for sum[" << S << "] = " << min[S] << endl;
}


Output:
Coins required for sum[11] = 3

DP Problem #4: Longest Increasing subsequence
    The Longest Increasing Subsequence problem is to find the longest increasing subsequence of a given sequence. Given a sequence S= {a1 , a2 , a3, a4, ............., an-1, an } we have to find a longest subset such that for all j and i,  ,  j < i in the subset aj < ai.


Example:
    Given sequence 3,5,2,7,1,5,3,8,0,9 find the longest increasing subsequence.
 
Solution:
#include

int main()
{
        const int N = 10;
        int A[N] = {3,5,2,7,1,5,3,8,0,9};
        int LS[N];

        for(int i=0;i
        {
                LS[i] = 1;
                for(int j=0;j
                {
                        if(A[j]<=LS[j])
                                LS[i] = LS[j]+1;
                }
        }
        int l = 0;
        for(int i=0;i
        {
                l = LS[i]>l?LS[i]:l;
        }
        cout << "Longest increasing subsequence :: " << l << endl;
}
 
Output:
Longest increasing subsequence :: 5


DP Problem #5: Longest common subsequence
    Given a sequence of elements, a subsequence of it can be obtained by removing zero or more elements from the sequence, preserving the relative order of the elements. Note that for a substring, the elements need to be contiguous in a given string, for a subsequence it need not be. Eg: S1="ABCDEFG" is the given string. "ACEG", "CDF" are subsequences, where as "AEC" is not.


Example:
    Given strings "XMJYAUZSS" and "MZJAWXU", find the longest common subsequence.


Solution:
#include

#define MAX 100

unsigned int C[MAX][MAX];

int lcs_length(char *X, char *Y)
{
        size_t M = strlen(X), N = strlen(Y);

        for(int i=0;i<=(int)M;i++)
                C[i][0] = 0;
        for(int j=0;j<=(int)N;j++)
                C[0][j] = 0;

        for(int i=1;i<=(int)M;i++)
        {
                for(int j=1;j<=(int)N;j++)
                {
                        if(X[i] == Y[j])
                                C[i][j] = C[i-1][j-1] + 1;
                        else
                                C[i][j] = C[i][j-1]>C[i-1][j]?C[i][j-1]:C[i-1][j];
                }
        }
        return C[M][N];
}

int main()
{
        char *X = "XMJYAUZSS", *Y = "MZJAWXU";

        cout << "Longest common subsequence :: " << lcs_length(X,Y) << endl;
}


Output:
Longest common subsequence :: 4