Lab-06 Dynamic Programming Report
Name : Syed Mahdi Hussain
ID : 2023-01-60-169
East West University
Department of Computer Science and Engineering
Course: CSE246 – Algorithms (Dynamic Programming Part-02)
Lab: 06
1. Objective
Implement and analyse five classic dynamic programming tasks by encapsulating each in its
own C++ function.
2. Tasks & Corresponding Functions
Task Function Name
Longest Increasing Subsequence (LIS) vector<int> lis(const vector<int>&)
Longest Strictly Decreasing Subsequence int lds(const vector<int>&)
(LDS)
Longest Common Subsequence (LCS) int lcs(const string&, const string&)
Longest Common Substring (LCSubstr) int lcs_substr(const string&, const string&)
Longest Palindromic Subsequence (LPS) int lps(const string&)
3. C++ Implementation
#include <bits/stdc++.h>
using namespace std;
// 1. Longest Increasing Subsequence (returns one LIS)
vector<int> lis(const vector<int>& a) {
int n = a.size();
vector<int> dp(n,1), parent(n,-1), seq;
int best = 1, idx = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < i; ++j) {
if(a[j] < a[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
parent[i] = j;
}
}
if(dp[i] > best) {
best = dp[i];
idx = i;
}
}
for(int cur = idx; cur != -1; cur = parent[cur])
seq.push_back(a[cur]);
reverse(seq.begin(), seq.end());
return seq;
}
// 2. Longest Strictly Decreasing Subsequence (returns length)
int lds(const vector<int>& a) {
int n = a.size(), best = 1;
vector<int> dp(n,1);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < i; ++j) {
if(a[j] > a[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
best = max(best, dp[i]);
}
return best;
}
// 3. Longest Common Subsequence (returns length)
int lcs(const string& S, const string& T) {
int m = S.size(), n = T.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
if(S[i-1] == T[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
// 4. Longest Common Substring (returns length)
int lcs_substr(const string& S, const string& T) {
int m = S.size(), n = T.size(), best = 0;
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) {
if(S[i-1] == T[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
best = max(best, dp[i][j]);
}
}
}
return best;
}
// 5. Longest Palindromic Subsequence (returns length)
int lps(const string& S) {
int n = S.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for(int i = 0; i < n; ++i) dp[i][i] = 1;
for(int len = 2; len <= n; ++len) {
for(int i = 0; i + len - 1 < n; ++i) {
int j = i + len - 1;
if(S[i] == S[j]) {
dp[i][j] = (len == 2 ? 2 : dp[i+1][j-1] + 2);
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i) cin >> a[i];
auto seq = lis(a);
cout << "LIS length: " << seq.size() << "\nSequence: ";
for(int x : seq) cout << x << " ";
cout << "\nLDS length: " << lds(a) << "\n";
string S, T;
cin >> S >> T;
cout << "LCS length: " << lcs(S, T) << "\n";
cout << "LCSubstring length: " << lcs_substr(S, T) << "\n";
cin >> S;
cout << "LPS length: " << lps(S) << "\n";
return 0;
}
4. Run
5. Time Complexity
- LIS, LDS, LPS: O(n²)
- LCS, LCSubstr: O(m·n)
