DEV Community

Dev Cookies
Dev Cookies

Posted on

📝 Blog 6: DP on Subsequences (Arrays & Strings)

🌟 Why This Pattern?

Many problems revolve around choosing or skipping elements in a sequence to form valid subsequences. The challenge comes from maintaining order and finding optimal properties (length, count, sum, lexicographic order, etc.).

Dynamic Programming shines here because:

  1. Overlapping subproblems exist (checking subsequences at different indexes).
  2. Optimal substructure appears (solution to prefix depends on smaller prefixes).

🔑 Core Ideas

  • Define dp[i] or dp[i][j] where state represents:

    • i → position in first string/array.
    • j → position in second string (if comparing).

  • Transitions:

    • Include current element.
    • Exclude current element.

  • Carefully manage base cases.

🏆 Problems & Solutions

1️⃣ Longest Increasing Subsequence (LIS)

Find the longest subsequence where elements are strictly increasing.

👉 Key Intuition:
For each element, check all previous ones smaller than it, then extend their LIS length.

public class LIS {
    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int maxLen = 1;

        for (int i = 0; i < n; i++) {
            dp[i] = 1; // every element is LIS of length 1
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lengthOfLIS(nums)); // 4 (2,3,7,101)
    }
}
Enter fullscreen mode Exit fullscreen mode

🔹 Variations:

  • Count number of LIS.
  • Print one actual LIS.
  • Apply patience sorting for O(n log n) version.

2️⃣ Longest Common Subsequence (LCS)

Given two strings, find the length of the longest subsequence that appears in both.

👉 Key Intuition:
At each step, either characters match → include in LCS, else → take max of excluding one.

public class LCS {
    public static int lcs(String a, String b) {
        int n = a.length(), m = b.length();
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.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];
    }

    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace")); // 3 (ace)
    }
}
Enter fullscreen mode Exit fullscreen mode

🔹 Variations:

  • Print actual LCS.
  • Shortest Common Supersequence.
  • Min Deletions to make strings equal.

3️⃣ Longest Palindromic Subsequence

Find the longest subsequence of a string that reads the same forward & backward.

👉 Key Intuition:
If chars match → expand both ends. Else → try removing one side.

public class LPS {
    public static int longestPalindromicSubsequence(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = 2 + dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(longestPalindromicSubsequence("bbbab")); // 4 ("bbbb")
    }
}
Enter fullscreen mode Exit fullscreen mode

4️⃣ Distinct Subsequences Count

Count number of distinct subsequences of s that equal t.

👉 Key Intuition:
At each step, either use matching character or skip it.

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

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

        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 dp[n][m];
    }

    public static void main(String[] args) {
        System.out.println(numDistinct("rabbbit", "rabbit")); // 3
    }
}
Enter fullscreen mode Exit fullscreen mode

5️⃣ Partition Problems (Subsequence Sum)

Check if array can be partitioned into two subsets with equal sum.

👉 Key Intuition:
Reduce to subset-sum problem.

public class PartitionEqualSubsetSum {
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 2 != 0) return false;

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println(canPartition(nums)); // true
    }
}
Enter fullscreen mode Exit fullscreen mode

🔥 More Problems You Should Practice

  • Minimum Deletions to Make Palindrome
  • Count Palindromic Subsequences
  • Shortest Palindrome Insertions
  • Max Sum Increasing Subsequence
  • Word Break (subsequence + dictionary check)

📌 Key Takeaways

  • Subsequence = skip or include → classic DP choice.
  • States often track index positions and transitions come from choice-making.
  • Problems differ in what you optimize: length, count, sum, or structure.

Top comments (0)