Given an array, find the length of the longest subsequence where elements are in strictly increasing order.

int longestIncreasingSubsequence(vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n, 1);
    for (int i = 1; i < n; ++i) {
        for (int k = 0; k < i; ++k) {
            if (arr[i] > arr[k]) {
                dp[i] = max(dp[i], dp[k] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

Longest Continuous Increasing Subsequence

Find the longest cnotiguous segment where each element is greater than the previous.

int findLengthOfLCIS(vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n, 1);
    for (int i = 1; i < n; ++i) {
        if (arr[i] > arr[i - 1]) {
            dp[i] = dp[i - 1] + 1;
        }
    }
    return *max_element(dp.begin(), dp.end());
}

Longest Common Subarray

Find the longest contiguous subarray common to two integer arrays.

Method 1: 2D DP with Padding

int findLength(vector<int>& a, vector<int>& b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int maxLength = 0;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                maxLength = max(maxLength, dp[i][j]);
            }
        }
    }
    return maxLength;
}

Method 2: Optimized with Rolling Array

int findLength(vector<int>& a, vector<int>& b) {
    int n = b.size();
    vector<int> dp(n + 1, 0);
    int maxLength = 0;
    for (int i = 0; i < a.size(); ++i) {
        for (int j = n; j > 0; --j) {
            if (a[i] == b[j - 1]) {
                dp[j] = dp[j - 1] + 1;
                maxLength = max(maxLength, dp[j]);
            } else {
                dp[j] = 0;
            }
        }
    }
    return maxLength;
}

Longest Common Subsequence

Find the longest subsequence common to two strings (not necessarily contiguous).

int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size(), n = s2.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 (s1[i - 1] == s2[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];
}

Subsequence Check (Is s a subsequence of t?)

bool isSubsequence(string s, 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] = dp[i][j - 1];
            }
        }
    }
    return dp[m][n] == m;
}

Maximum Subarray Sum

Kadane’s algorithm implemented via DP: find the contiguous subarray with largest sum.

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
    for (int i = 1; i < n; ++i) {
        dp[i] = max(nums[i], dp[i - 1] + nums[i]);
    }
    return *max_element(dp.begin(), dp.end());
}

Distinct Subsequences

Count the number of ways to form string t by deleting characters from string s.

int numDistinct(string s, string t) {
    int m = s.size(), n = t.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; ++i) dp[i][0] = 1;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] += dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
}

Minimum Deletion to Make Strings Equal

Find minimum deletions required to make two strings identical.

int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; ++i) dp[i][0] = i;
    for (int j = 0; j <= n; ++j) dp[0][j] = j;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2});
            }
        }
    }
    return dp[m][n];
}

Edit Distance

Minimum operations (insert, delete, replace) to convert one string to another.

int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; ++i) dp[i][0] = i;
    for (int j = 0; j <= n; ++j) dp[0][j] = j;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1});
            }
        }
    }
    return dp[m][n];
}

Count Palindromic Substrings

Count all substrings that are palindromes.

int countSubstrings(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int count = 0;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i; j < n; ++j) {
            if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                ++count;
            }
        }
    }
    return count;
}

Longest Palindromic Subsequence

Find the longest subsequence that reads the same forwards and backwards.

int longestPalindromeSubseq(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 i = n - 1; i >= 0; --i) {
        for (int j = i + 1; j < n; ++j) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}