📝 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]:

1. Pick it → contribute to subsequence.
2. 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.

---

🔹 5. Real-World Uses

• Text diffing (git diff, plagiarism check) → LCS.
• Spell-check/autocorrect → Edit Distance.
• DNA sequence matching → LCS, Edit Distance.
• Recommendation systems → LIS-type ranking.
• Compression algorithms → repeated subsequences.

---

🔹 6. Interview Tips

• Always clarify subsequence vs substring.
• For 2-string problems → think 2D DP.
• If asked for “min operations” → try LCS or Edit Distance logic.
• If asked for “count ways” → usually DP counting paths.
• Keep reusable templates ready (like LCS).

---