📝 Blog 5: DP on Subsequences (Patterns in Arrays/Strings)

🔹 1. Why Subsequence DP?

A subsequence is formed by deleting elements (or characters) without changing the relative order.
Example: "ace" is a subsequence of "abcde", but "aec" is not.
Many DP problems boil down to:
- Should I include this element in my subsequence or skip it?
- Solve recursively → store results → optimize with DP.
These problems usually have a Pick / Not Pick choice.

🔹 2. Core Template for Subsequence DP

For each element arr[i] or character s[i]:

Pick it → contribute to subsequence.
Skip it → move ahead.

DP stores the best/maximum/minimum/count result for each choice.

🔹 3. Classic Subsequence DP Problems (with Code)

Let’s cover a wide variety of problems — from basic to advanced.

✅ Example 1: Longest Increasing Subsequence (LIS)

Problem: Find the length of the longest increasing subsequence in an array.

Idea:

For each element, check all smaller elements before it.
Extend LIS ending at that element.

Code (O(N²)):

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int maxLen = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

🔹 Variation:

Max Sum Increasing Subsequence → instead of +1, add nums[i].

✅ Example 2: Longest Common Subsequence (LCS)

Problem: Find the longest subsequence common to two strings.

Idea:

Compare last characters.
If equal → add 1 + result for previous indices.
Else → max of skipping one from either string.

Code:

public int lcs(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[][] dp = new int[n+1][m+1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = 1 + dp[i-1][j-1];
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[n][m];
}

🔹 Variations:

Longest Palindromic Subsequence → LCS between s and reverse(s).
Shortest Common Supersequence → len(s1) + len(s2) - LCS(s1, s2).

✅ Example 3: Edit Distance (Levenshtein)

Problem: Minimum insert/delete/replace to convert word1 → word2.

Idea:

If last characters are equal → no operation needed.
Else → consider insert, delete, replace.
Take minimum.

Code:

public int minDistance(String word1, String word2) {
    int n = word1.length(), m = word2.length();
    int[][] dp = new int[n+1][m+1];

    for (int i = 0; i <= n; i++) dp[i][0] = i; // delete
    for (int j = 0; j <= m; j++) dp[0][j] = j; // insert

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (word1.charAt(i-1) == word2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i-1][j],     // delete
                               Math.min(dp[i][j-1],    // insert
                                        dp[i-1][j-1]));// replace
            }
        }
    }
    return dp[n][m];
}

✅ Example 4: Count Subsequences with Target Sum

Problem: Count subsets of an array with sum = target.

Idea:

For each element:
- Include → add to sum.
- Exclude → skip.

Code:

public int countSubsets(int[] nums, int target) {
    int n = nums.length;
    int[][] dp = new int[n+1][target+1];
    dp[0][0] = 1; // base case

    for (int i = 1; i <= n; i++) {
        for (int sum = 0; sum <= target; sum++) {
            dp[i][sum] = dp[i-1][sum]; // exclude
            if (sum >= nums[i-1]) {
                dp[i][sum] += dp[i-1][sum - nums[i-1]]; // include
            }
        }
    }
    return dp[n][target];
}

✅ Example 5: Distinct Subsequences (LeetCode 115)

Problem: Count how many subsequences of s equal t.

Idea:

If chars match → two options:
- Use the char.
- Skip the char.
Else → skip only.

Code:

public int numDistinct(String s, String t) {
    int n = s.length(), m = t.length();
    long[][] dp = new long[n+1][m+1];

    for (int i = 0; i <= n; i++) dp[i][0] = 1; // empty t

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return (int) dp[n][m];
}

✅ Example 6: Minimum Deletions to Make a Palindrome

Idea:

Find Longest Palindromic Subsequence (LPS).
Answer = length - LPS.

Code:

public int minDeletions(String s) {
    String rev = new StringBuilder(s).reverse().toString();
    int lps = lcs(s, rev); // reuse LCS
    return s.length() - lps;
}

✅ Example 7: Maximum Sum Increasing Subsequence

Idea:

Like LIS but track sums.

Code:

public int maxSumLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    int maxSum = nums[0];

    for (int i = 0; i < n; i++) {
        dp[i] = nums[i];
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + nums[i]);
            }
        }
        maxSum = Math.max(maxSum, dp[i]);
    }
    return maxSum;
}

🔹 4. Optimization Techniques

Space Optimization: Use 1D arrays when only last row/column is needed (e.g., LCS, Edit Distance).
Binary Search: Optimize LIS to O(N log N).
Bitmask DP: Useful when N ≤ 20.
String Reverse Trick: For palindrome problems.