print lcs using dp

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

string str1,str2;
int CS[100][100];

int LCS(int str1_len,int str2_len)
{
    for(int i=1;i<=str1_len;i++)
    {
        for(int j=1;j<=str2_len;j++)
        {
            if(str1[i-1] == str2[j-1])
                CS[i][j] = 1 + CS[i-1][j-1];
            else
                CS[i][j] = max(CS[i-1][j],CS[i][j-1]);
        }
    }
}

int main()
{
    stack<char>stk;
    int first_start,second_start;
    cin>>str1>>str2;
    LCS(str1.size(),str2.size());
    cout<<"The LCS of these string = "<<CS[str1.size()][str2.size()]<<endl;


    for(int i=0;i<=str1.size();i++)
    {
        for(int j=0;j<=str2.size();j++)
            cout<<CS[i][j]<<" ";
        cout<<endl;
    }

    int mx = CS[str1.size()][str2.size()];
    for(int l = str1.size();l>=1;l--)
    {
        if(CS[l][str2.size()]==mx)
        {
            int i = l;
            int j = str2.size();
            while(j>0 && i>0)
            {
                if(CS[i][j] == CS[i][j-1])
                    j = j-1;
                else if(CS[i][j] == CS[i-1][j])
                    i = i-1;
                else
                {
                    stk.push(str2[j-1]);   /// Alternate way stk.push(str1[i-1])
                    i = i-1;
                    j = j-1;
                }
            }

            while(!stk.empty())
            {
                cout<<stk.top();
                stk.pop();
            }
            cout<<endl;
        }
    }
    return 0;
}