Lab
Program 1: Longest common Subsequence
#include <iostream>
#include<vector>
using namespace std;
void lcs(string s1, string s2) {
int n = s1.size();
int m = s2.size();
vector < vector < int >> dp(n + 1, vector < int > (m + 1, 0));
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
for (int i = 0; i <= m; i++) {
dp[0][i] = 0;
for (int ind1 = 1; ind1 <= n; ind1++) {
for (int ind2 = 1; ind2 <= m; ind2++) {
if (s1[ind1 - 1] == s2[ind2 - 1])
dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1];
else
dp[ind1][ind2] = 0 + max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
}
int len = dp[n][m];
int i = n;
int j = m;
int index = len - 1;
string str = "";
for (int k = 1; k <= len; k++) {
str += "$"; // dummy string
while (i > 0 && j > 0) {
if (s1[i - 1] == s2[j - 1]) {
str[index] = s1[i - 1];
index--;
i--;
j--;
} else if (s1[i - 1] > s2[j - 1]) {
i--;
} else j--;
cout << str;
int main() {
string s1,s2;
cout << "Enter the first string : ";
cin >> s1;
cout << "Enter the second string : ";
cin >> s2;
cout << "The Longest Common Subsequence is ";
lcs(s1, s2);
OUTPUT:
Program 2: Matrix Chain Multiplication
#include <iostream>
#include<vector>
using namespace std;
int f(vector<int>& arr, int i, int j, vector<vector<int>>& dp){
if(i == j)
return 0;
if(dp[i][j]!=-1)
return dp[i][j];
int mini = INT_MAX;
for(int k = i; k<= j-1; k++){
int ans = f(arr,i,k,dp) + f(arr, k+1,j,dp) + arr[i-1]*arr[k]*arr[j];
mini = min(mini,ans);
return mini;
int matrixMultiplication(vector<int>& arr, int N){
vector<vector<int>> dp(N,vector<int>(N,-1));
int i =1;
int j = N-1;
return f(arr,i,j,dp);
int main() {
int n;
cout << "Enter the size of the array : ";
cin >> n;
vector<int> arr(n);
for(int i = 0;i < n;i++) {
cin >> arr[i];
cout<<"The minimum number of operations is "<<matrixMultiplication(arr,n);
return 0;
}
OUTPUT:
