DYNAMIC PROGRAMMING
NAME - Harshit Raj
Roll No. - Btech/10257/18
Class – CSE ‘A’
Assignment -
Question 1)
Longest Common Subsequence
Code-
//Longest Common Subsequence
//lcs of 'AABCABB' and 'BCABABB'
//assignment 2
#include <bits/stdc++.h>
using namespace std;
int max(int a,int b){
return (a>b)?a:b;
}
void lcs(char* X,char* Y,int m,int n){
int L[m+1][n+1]; //m and n are length of string X and Y
for(int i=0;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
L[i][j]=0;
}
}
cout<<"DP Table - "<<endl;
//Building dp table from length 0 to length m of string X
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
//Optimal Substructure
if(i==0||j==0){
L[i][j]=0;
}
else if(X[i-1]==Y[j-1]){
L[i][j]=1 + L[i-1][j-1];
}
else{
L[i][j]=max(L[i-1][j],L[i][j-1]);
}
}
cout<<"Iteration - "<< i+1<<endl;
for(int j=0;j<=m;j++)
{
for(int h=0;h<=n;h++)
{
cout<<L[j][h]<<" ";
}
cout<<endl;
}
}
cout<<"Length of LCS is: "<<L[m][n]<<endl;
//to print lcs
int i=m,j=n,index=L[m][n];
char lcs[index+1];
lcs[index]='\0';
while(i>0 && j>0){
if(X[i-1] == Y[j-1]){
lcs[index-1]=X[i-1];
i--;
j--;
index--;
}
else if(L[i-1][j]>L[i][j-1]){
i--;
}
else {
j--;
}
}
cout<<"LCS of given sequence "<<X<<" is: "<<lcs<<endl;
}
int main(){
cout<<"Longest Common Subsequence"<<endl;
char X[]="AABCABB";
char Y[]="BCABABB";
cout<<"String X: "<<X<<endl;
cout<<"String Y: "<<Y<<endl;
int m = strlen(X);
int n = strlen(Y);
lcs(X,Y,m,n);
}
Output:
Longest Common Subsequence
String X: AABCABB
String Y: BCABABB
DP Table -
Iteration - 1
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
Iteration - 2
00000000
00011111
00000000
00000000
00000000
00000000
00000000
00000000
Iteration - 3
00000000
00011111
00011222
00000000
00000000
00000000
00000000
00000000
Iteration - 4
00000000
00011111
00011222
01112233
00000000
00000000
00000000
00000000
Iteration - 5
00000000
00011111
00011222
01112233
01222233
00000000
00000000
00000000
Iteration - 6
00000000
00011111
00011222
01112233
01222233
01233333
00000000
00000000
Iteration - 7
00000000
00011111
00011222
01112233
01222233
01233333
01234444
00000000
Iteration - 8
00000000
00011111
00011222
01112233
01222233
01233333
01234444
01234455
Length of LCS is: 5
LCS of given sequence AABCABB is: BCABB
Question 2)
Longest Palindromic Subsequence
Code:
//Longest Palindromic Subsequence
//lps of 'AABCABB'
//assignment 3
#include <bits/stdc++.h>
using namespace std;
int max(int a,int b){
return (a>b)?a:b;
void lps(char *seq,int m){
int L[m+1][m+1] ;// Create a table to store results of subproblems
int i , cl , j;
for(i=0;i<m+1;i++){
for(j=0;j<m+1;j++){
L[i][j] = 0;
cout<<"DP Table - "<<endl;
for(i=0;i<=m;i++){
L[i][i] = 1; // Strings of length 1 are palindrome of lentgh 1
}
//Building dp table from string of length 2 to n
int t=0;
for(cl=2;cl<=m;cl++){
for(i=0;i<=m-cl;i++){
//Optimal substructure
j=i+cl-1;
if(seq[i]==seq[j]&&cl==2){
L[i][j] = 2;
else if(seq[i]==seq[j])
L[i][j] = 2 + L[i+1][j-1];
else
L[i][j] = max(L[i][j-1],L[i+1][j]);
cout<<"Iteration - "<< t+1<<endl;
t++;
for(j=0;j<m;j++)
{
for(int h=0;h<m;h++)
cout<<L[j][h]<<" ";
cout<<endl;
cout<<"Length of LPS is "<<L[0][m-1]<<endl;
// to print lps. lcs of a string and its reverse is lps of that string
void lcs(char* seq,char *rev,int m){
int L[m+1][m+1];
int i,j;
for(i=0;i<=m;i++){
for(j=0;j<=m;j++){
if(i==0 || j==0){
L[i][j] = 0;
else if(seq[i-1]==rev[j-1]){
L[i][j] = 1 + L[i-1][j-1];
else{
L[i][j] = max(L[i][j-1],L[i-1][j]);
int index = L[m][m];
i=j=m;
char lps[index+1];
lps[index] = '\0';
while(i>0 && j>0){
if(seq[i-1] == rev[j-1]){
lps[index-1] = seq[i-1];
index--;
i--;
j--;
else if(L[i-1][j]>L[i][j-1]){
i--;
else {
j--;
cout<<"LPS of given sequence "<< seq << " is "<<lps<<endl;
int main(){
cout<<"Longest Palindromic Subsequence"<<endl;
char seq[]="AABCABB";
cout<<"String : "<<seq<<endl;
char rev[]="BBACBAA";
int m = strlen(seq);
lps(seq,m);
lcs(seq,rev,m);
return 0;
Output:
Longest Palindromic Subsequence
String : AABCABB
DP Table -
Iteration - 1
1200000
0110000
0011000
0001100
0000110
0000012
0000001
Iteration - 2
1220000
0111000
0011100
0001110
0000112
0000012
0000001
Iteration - 3
1222000
0111300
0011130
0001112
0000112
0000012
0000001
Iteration - 4
1222300
0111330
0011133
0001112
0000112
0000012
0000001
Iteration - 5
1222330
0111333
0011133
0001112
0000112
0000012
0000001
Iteration - 6
1222333
0111333
0011133
0001112
0000112
0000012
0000001
Length of LPS is 3
LPS of given sequence AABCABB is BBB
Question 3)
Matrix Chain Multiplication(MCM)
Code:
//Matrix Chain Multiplication
//4 matrices A,B,C,D dimensions are 5x7 , 7x9 , 9x3 , 3x5
//assignment 5
#include <bits/stdc++.h>
using namespace std;
#define n 5
#define MAX 99999
//print order of matrix multiplication
void print(int i , int j, int m, int *S , char &name)
if(i == j){
cout << name++;
return;
cout<<"(";
print(i , *((S+i*m)+j) , m ,S ,name);
print(*((S+i*m)+j)+1 , j , m , S , name );
cout<<")";
void mcm(int p[],int m[][n], int S[][n]){
int i,d,j,k,min,q;
//Building up dp table from length 2 to n
for(d=1;d<n-1;d++){
for(i=1;i<n-d;i++){
j=i+d;
min = MAX;
for(k=i;k<=j-1;k++){
//Optimal Substructure
q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
if( q < min ){
min = q;
S[i][j] = k;
m[i][j] = min;
cout <<"Iteration - "<< d<<endl;
for(j=1;j<n;j++)
for(int h=1;h<n;h++)
cout<<m[j][h]<<" ";
}
cout<<endl;
char name = 'A';
cout << "Optimal matrix chain multiplication is ";
print(1 , n-1 , n , (int*)S , name);
cout << "\nOptimal Cost is " << m[1][n-1] << endl;
int main(){
int p[]={5,7,9,3,5};
cout<<"Array - ";
for(int i=0;i<sizeof(p)/sizeof(int);i++){
cout<<p[i]<<" ";
cout<<endl;
int m[n][n]={0};// Create a table to store results of subproblems
int S[n][n]={0};// Create a table to print the order of matrix multiplication
mcm(p,m,S);
}
Output:
Array - 5 7 9 3 5
Iteration - 1
0 315 0 0
0 0 189 0
0 0 0 135
0000
Iteration - 2
0 315 294 0
0 0 189 294
0 0 0 135
0000
Iteration - 3
0 315 294 369
0 0 189 294
0 0 0 135
0000
Optimal matrix chain multiplication is ((A(BC))D)
Optimal Cost is 369
Question 4)
Maximum Subarray Problem
Code:
//Maximum subarray problem using Dynamic Programming
//Assignment 12
#include <bits/stdc++.h>
using namespace std;
#define MIN -99999
typedef long long ll;
int main(){
cout<<"Enter size of the array"<<endl;
ll n;
cin>>n;
cout<<"Enter array"<<endl;
ll arr[n];
for (ll i=0;i<n;i++){
cin>>arr[i];
//store maximum sum in max_so_far.calculate sum for each element and store in
max_ending _here.Then compare.
//if max_ending_here is negative make it 0 and shift to next element in array
ll max_so_far = INT_MIN , max_ending_here = 0 , start=0 , end=0 , s=0;
for(ll i=0;i<n;i++){
//Optimal Substructure
max_ending_here += arr[i];
if(max_ending_here > max_so_far){
max_so_far = max_ending_here;
start = s;
end = i;
else if(max_ending_here < 0){
max_ending_here = 0;
s = s+1;
cout << "Iteration : "<<i+1<<endl;
for(ll i=start+1 ; i<=end;i++){
cout << arr[i] << " " ;
}
cout<<endl;
cout << "Required subarray is :";
for(ll i=start+1 ; i<=end;i++){
cout << arr[i] << " " ;
cout<<endl;
cout << "Maximum sum is : "<<max_so_far <<endl;
Output:
Enter size of the array
15
Enter array
3 50 45 -21 -33 0 9 -56 9 80 76 -88 56 78 69
Iteration : 1
Iteration : 2
50
Iteration : 3
50 45
Iteration : 4
50 45
Iteration : 5
50 45
Iteration : 6
50 45
Iteration : 7
50 45
Iteration : 8
50 45
Iteration : 9
50 45
Iteration : 10
50 45
Iteration : 11
45 -21 -33 0 9 -56 9 80 76
Iteration : 12
45 -21 -33 0 9 -56 9 80 76
Iteration : 13
45 -21 -33 0 9 -56 9 80 76
Iteration : 14
45 -21 -33 0 9 -56 9 80 76 -88 56 78
Iteration : 15
45 -21 -33 0 9 -56 9 80 76 -88 56 78 69
Required subarray is :45 -21 -33 0 9 -56 9 80 76 -88 56 78 69
Maximum sum is : 280
Question 5)
Element appearing maximum number of times
Code:
//Element which appears maximum number of times.
//Assignment 14
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 99999
int main(){
cout<< "Enter size of array"<<endl;
ll n;
cin>>n;
ll arr[n] , PMax=0 ,NMax=0;
// to keep count of positive numbers and negative numbers.Index of array
denotes the number itself.
ll count[n] = {0} , negative_count[n] = {0} , Pnumber = 0 , Nnumber = 0;
cout<<"Enter array for finding maximum occurence of an element"<<endl;
for (ll i=0;i<n;i++){
cin >> arr[i];
for(ll i = 0;i < n; i++){
//Optimal Substructure
if (arr[i] >= 0){
count [arr[i]] += 1;
if ( count[arr[i]] > PMax ){
PMax = count[arr[i]];
Pnumber = arr[i];
else{
negative_count[abs(arr[i])] += 1;
if( negative_count[abs(arr[i])] > NMax){
NMax = negative_count[abs(arr[i])];
Nnumber = arr[i];
if( PMax > NMax){
cout << "The number appearing maximum number of times is "<<Pnumber
<<" and it appears "<<PMax << " times"<< endl;
else{
cout << "The number appearing maximum number of times is "<<Nnumber
<<" and it appears "<<NMax << " times"<< endl;
return 0;
Output:
Enter size of array
14
Enter array for finding maximum occurence of an element
41521598653247
The number appearing maximum number of times is 5 and it appears 3 times.
__________________________________________________________________
__________
