Minimum coins needed to make change

#include <iostream>

#include <climits>

using namespace std;

int mem[50][50];

int min(int a, int b)

{

    return a<b ? a:b;

}

int minCoinChange(int c[], int n, int val)

{

    int minCoins = INT_MAX;

    for(int i=0;i<n;i++)

    {

        mem[i][0] = 0;

        int j=0;

        for(;j<=val;j++)

        {

            if(i > 0)

            {

                if(j>=c[i])

                    mem[i][j] = min(mem[i-1][j], 1 + mem[i][j-c[i]]);

                else

                    mem[i][j] = mem[i-1][j];

                

            }

            else

            {

                if(j < c[i])

                    mem[i][j] = 0;

                else

                    mem[i][j] = 1 + j - c[i] ;

                    

            }

        }

        if(minCoins > mem[i][j-1])

            minCoins = mem[i][j-1];

    }

    

    return minCoins;

}

void printCoins(int c[], int n)

{

    for(int i=0;i<n;i++)

        cout << c[i] << ", ";

}

int main() {

// your code goes here

int c[] = {1,6,10};

for(int i=0; i<30; i++)

{

    int val = i;

    cout << "minimum coins required to make change of " << val << " using coins ";

    printCoins(c, sizeof(c)/sizeof(c[0]));

    cout << " = " << minCoinChange(c, sizeof(c)/sizeof(c[0]), val) << endl;

}

return 0;

}

Output -

minimum coins required to make change of 0 using coins 1, 6, 10,  = 0

minimum coins required to make change of 1 using coins 1, 6, 10,  = 1

minimum coins required to make change of 2 using coins 1, 6, 10,  = 2

minimum coins required to make change of 3 using coins 1, 6, 10,  = 3

minimum coins required to make change of 4 using coins 1, 6, 10,  = 4

minimum coins required to make change of 5 using coins 1, 6, 10,  = 5

minimum coins required to make change of 6 using coins 1, 6, 10,  = 1

minimum coins required to make change of 7 using coins 1, 6, 10,  = 2

minimum coins required to make change of 8 using coins 1, 6, 10,  = 3

minimum coins required to make change of 9 using coins 1, 6, 10,  = 4

minimum coins required to make change of 10 using coins 1, 6, 10,  = 1

minimum coins required to make change of 11 using coins 1, 6, 10,  = 2

minimum coins required to make change of 12 using coins 1, 6, 10,  = 2

minimum coins required to make change of 13 using coins 1, 6, 10,  = 3

minimum coins required to make change of 14 using coins 1, 6, 10,  = 4

minimum coins required to make change of 15 using coins 1, 6, 10,  = 5

minimum coins required to make change of 16 using coins 1, 6, 10,  = 2

minimum coins required to make change of 17 using coins 1, 6, 10,  = 3

minimum coins required to make change of 18 using coins 1, 6, 10,  = 3

minimum coins required to make change of 19 using coins 1, 6, 10,  = 4

minimum coins required to make change of 20 using coins 1, 6, 10,  = 2

minimum coins required to make change of 21 using coins 1, 6, 10,  = 3

minimum coins required to make change of 22 using coins 1, 6, 10,  = 3

minimum coins required to make change of 23 using coins 1, 6, 10,  = 4

minimum coins required to make change of 24 using coins 1, 6, 10,  = 4

minimum coins required to make change of 25 using coins 1, 6, 10,  = 5

minimum coins required to make change of 26 using coins 1, 6, 10,  = 3

minimum coins required to make change of 27 using coins 1, 6, 10,  = 4

minimum coins required to make change of 28 using coins 1, 6, 10,  = 4

minimum coins required to make change of 29 using coins 1, 6, 10,  = 5

Length of shortest common supersequence

 #include <iostream>

#include <cstring>

using namespace std;

//shortest common supersequence between 2 strings = l1 + l2 - LCS

int mem[20][20];

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

int scs(char s1[], int l1, char s2[], int l2)

{

    for(int i=0; i<l1; i++)

    {

        for(int j=0; j<l2; j++)

        {

            if(s1[i] == s2[j])

            {

                mem[i][j] = (j==0)?1:1 + mem[i][j-1];

            }

            else

            {

                mem[i][j] = max((j>0)?mem[i][j-1]:0, (i>0)?mem[i-1][j]:0);

            }

        }

    }

    return l1+l2-mem[l1-1][l2-1];

}

int main() {

// your code goes here

memset(mem, -1, sizeof(mem));

char a[] = "subsequence";

char b[] = "queue";

int len = scs(a,strlen(a), b, strlen(b));

cout << "Length of shortest common supersequence between " << a << " and " << b << " is=" << len;

return 0;

}

Output:

Length of shortest common supersequence between subsequence and queue is=12

Longest increasing subsequence

 #include <iostream>

#include <cstring>

using namespace std;

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

void longestIncreasingSubsequence(int a[], int n)

{

    int l[n];

    for(int i=0;i<n;i++) 

        l[i] = 1;

    for(int j=1, i=0; j<n; j++)

    {

        while(i<j)

        {

            if(a[i] < a[j])

            {

                l[j] = max(l[j], 1+l[i]);

                cout << "l[j]=" << l[j] << endl;

            }

            i++;

        }

        i=0;

    }

    

    cout<< "length of longest increasing subsequence is " << l[n-1] ;

}

int main() {

// your code goes here

int a[] = {3, 4, -1, 0, 6, 2, 3};

longestIncreasingSubsequence(a, sizeof(a)/sizeof(a[0]));

return 0;

}

Output:

l[j]=2

l[j]=2

l[j]=2

l[j]=3

l[j]=3

l[j]=3

l[j]=2

l[j]=3

l[j]=2

l[j]=3

l[j]=4

length of longest increasing subsequence is 4