[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":93,"_73":94,"_35":95},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",44,"title","Classic DP Patterns","slug","algorithms-part-17-classic-dp-patterns","excerpt","Solve canonical DP problems: 0/1 and unbounded knapsack, Longest Common Subsequence, Longest Increasing Subsequence, edit distance, and matrix chain multiplication.","# Part 17: Classic DP Patterns - Knapsack, LCS, LIS, and Edit Distance\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Time to Read | 40 minutes |\n| Prerequisites | Part 16 (DP Foundations) |\n| Key Concepts | Knapsack, LCS, LIS, Edit Distance, Matrix Chain |\n| Difficulty | ⭐⭐⭐ (Intermediate) |\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ CLASSIC DP PATTERNS │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ KNAPSACK FAMILY SEQUENCE PROBLEMS │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ 0/1 Knapsack │ │ LCS │ │\n│ │ ─────────────── │ │ ─────────────── │ │\n│ │ Take or leave │ │ Match chars │ │\n│ │ each item │ │ in both strings │ │\n│ │ │ │ │ │\n│ │ Unbounded │ │ LIS │ │\n│ │ ─────────────── │ │ ─────────────── │ │\n│ │ Unlimited copies│ │ Increasing │ │\n│ │ of each item │ │ subsequence │ │\n│ └─────────────────┘ └─────────────────┘ │\n│ │\n│ STRING OPERATIONS OPTIMIZATION │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ Edit Distance │ │ Matrix Chain │ │\n│ │ ─────────────── │ │ ─────────────── │ │\n│ │ Insert, Delete │ │ Optimal │ │\n│ │ Replace │ │ parenthesization│ │\n│ │ │ │ │ │\n│ │ Used in: diff, │ │ Used in: │ │\n│ │ spell check, │ │ query planning, │ │\n│ │ DNA alignment │ │ expression eval │ │\n│ └─────────────────┘ └─────────────────┘ │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🎯 What You'll Learn\n\nAfter completing this article, you will be able to:\n\n1. **Solve knapsack variants**: 0/1, unbounded, bounded, subset sum\n2. **Find LCS**: Longest common subsequence between strings\n3. **Compute LIS**: Longest increasing subsequence in O(n log n)\n4. **Calculate edit distance**: Transform one string to another\n5. **Optimize matrix chains**: Find optimal multiplication order\n\n---\n\n## 🔥 Production Story: The Code Review Diff Engine\n\nA code review platform needed to show differences between file versions. Their naive diff algorithm was timing out on large files.\n\n### The Problem\n\n```java\n// ❌ Naive approach - find differences line by line\npublic class NaiveDiff {\n public List diff(String[] oldLines, String[] newLines) {\n List changes = new ArrayList<>();\n\n // O(n*m) comparisons for each potential match\n // Plus backtracking to find optimal alignment\n // Result: exponential time on large files\n\n return findChanges(oldLines, newLines, 0, 0, changes);\n }\n\n // Exponential recursive search...\n}\n```\n\nFiles with 10,000 lines were timing out after 30 seconds.\n\n### The Solution: LCS-Based Diff\n\n```java\n// ✅ LCS-based diff - O(n*m) time\npublic class LCSDiff {\n public List diff(String[] oldLines, String[] newLines) {\n int n = oldLines.length, m = newLines.length;\n\n // Step 1: Find LCS using DP\n int[][] dp = new int[n + 1][m + 1];\n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= m; j++) {\n if (oldLines[i - 1].equals(newLines[j - 1])) {\n dp[i][j] = dp[i - 1][j - 1] + 1;\n } else {\n dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);\n }\n }\n }\n\n // Step 2: Backtrack to find actual LCS\n Set oldInLCS = new HashSet<>();\n Set newInLCS = new HashSet<>();\n backtrack(dp, oldLines, newLines, n, m, oldInLCS, newInLCS);\n\n // Step 3: Lines NOT in LCS are changes\n List changes = new ArrayList<>();\n for (int i = 0; i < n; i++) {\n if (!oldInLCS.contains(i)) {\n changes.add(new Change(ChangeType.DELETE, i, oldLines[i]));\n }\n }\n for (int j = 0; j < m; j++) {\n if (!newInLCS.contains(j)) {\n changes.add(new Change(ChangeType.ADD, j, newLines[j]));\n }\n }\n\n return changes;\n }\n\n private void backtrack(int[][] dp, String[] old, String[] new_,\n int i, int j, Set oldIdx, Set newIdx) {\n if (i == 0 || j == 0) return;\n\n if (old[i - 1].equals(new_[j - 1])) {\n oldIdx.add(i - 1);\n newIdx.add(j - 1);\n backtrack(dp, old, new_, i - 1, j - 1, oldIdx, newIdx);\n } else if (dp[i - 1][j] > dp[i][j - 1]) {\n backtrack(dp, old, new_, i - 1, j, oldIdx, newIdx);\n } else {\n backtrack(dp, old, new_, i, j - 1, oldIdx, newIdx);\n }\n }\n}\n```\n\n### The Impact\n\n| File Size | Before | After |\n|-----------|--------|-------|\n| 100 lines | 50ms | 2ms |\n| 1,000 lines | 5s | 20ms |\n| 10,000 lines | Timeout | 200ms |\n| 100,000 lines | Impossible | 2s |\n\n---\n\n## 🔬 Deep Dive: 0/1 Knapsack\n\n### The Problem\n\nGiven items with weights and values, maximize value within weight capacity.\n\n### 🎮 Try It Yourself\n\nWatch how the DP table fills up step by step:\n\n```visualizer-dp\nalgorithm: knapsack\ncontrols: true\n```\n\n### Visual Representation\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ 0/1 KNAPSACK │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Items: [📱, 💻, 📷, 🎧] │\n│ Weights: [1, 4, 3, 2] │\n│ Values: [15, 30, 20, 10] │\n│ Capacity: 5 │\n│ │\n│ State: dp[i][w] = max value using items 0..i-1 with capacity w │\n│ │\n│ Transition: │\n│ dp[i][w] = max( │\n│ dp[i-1][w], // Don't take item i │\n│ dp[i-1][w-wt[i]] + val[i] // Take item i (if fits) │\n│ ) │\n│ │\n│ Answer: dp[n][W] = 35 (take 📱 and 💻: weights 1+4=5) │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Implementation\n\n```java\npublic class Knapsack01 {\n // Standard 2D DP - O(nW) time, O(nW) space\n public int knapsack(int[] weights, int[] values, int capacity) {\n int n = weights.length;\n int[][] dp = new int[n + 1][capacity + 1];\n\n for (int i = 1; i <= n; i++) {\n for (int w = 0; w <= capacity; w++) {\n // Option 1: Don't take item i\n dp[i][w] = dp[i - 1][w];\n\n // Option 2: Take item i (if it fits)\n if (weights[i - 1] <= w) {\n dp[i][w] = Math.max(dp[i][w],\n dp[i - 1][w - weights[i - 1]] + values[i - 1]);\n }\n }\n }\n\n return dp[n][capacity];\n }\n\n // Space-optimized - O(W) space\n public int knapsackOptimized(int[] weights, int[] values, int capacity) {\n int[] dp = new int[capacity + 1];\n\n for (int i = 0; i < weights.length; i++) {\n // Traverse RIGHT to LEFT to avoid using updated values\n for (int w = capacity; w >= weights[i]; w--) {\n dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);\n }\n }\n\n return dp[capacity];\n }\n\n // Reconstruct which items were selected\n public List knapsackWithItems(int[] weights, int[] values, int capacity) {\n int n = weights.length;\n int[][] dp = new int[n + 1][capacity + 1];\n\n // Fill DP table\n for (int i = 1; i <= n; i++) {\n for (int w = 0; w <= capacity; w++) {\n dp[i][w] = dp[i - 1][w];\n if (weights[i - 1] <= w) {\n dp[i][w] = Math.max(dp[i][w],\n dp[i - 1][w - weights[i - 1]] + values[i - 1]);\n }\n }\n }\n\n // Backtrack to find items\n List items = new ArrayList<>();\n int w = capacity;\n for (int i = n; i > 0 && w > 0; i--) {\n if (dp[i][w] != dp[i - 1][w]) {\n items.add(i - 1); // Item i-1 was taken\n w -= weights[i - 1];\n }\n }\n\n return items;\n }\n}\n```\n\n### Knapsack Variants\n\n```java\npublic class KnapsackVariants {\n // Unbounded Knapsack - unlimited copies of each item\n public int unboundedKnapsack(int[] weights, int[] values, int capacity) {\n int[] dp = new int[capacity + 1];\n\n for (int w = 1; w <= capacity; w++) {\n for (int i = 0; i < weights.length; i++) {\n if (weights[i] <= w) {\n dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);\n }\n }\n }\n\n return dp[capacity];\n }\n\n // Subset Sum - can we make exact sum?\n public boolean subsetSum(int[] nums, int target) {\n boolean[] dp = new boolean[target + 1];\n dp[0] = true;\n\n for (int num : nums) {\n for (int s = target; s >= num; s--) {\n dp[s] = dp[s] || dp[s - num];\n }\n }\n\n return dp[target];\n }\n\n // Partition Equal Subset - can we split into two equal halves?\n public boolean canPartition(int[] nums) {\n int sum = Arrays.stream(nums).sum();\n if (sum % 2 != 0) return false;\n\n return subsetSum(nums, sum / 2);\n }\n\n // Count subsets with given sum\n public int countSubsets(int[] nums, int target) {\n int[] dp = new int[target + 1];\n dp[0] = 1;\n\n for (int num : nums) {\n for (int s = target; s >= num; s--) {\n dp[s] += dp[s - num];\n }\n }\n\n return dp[target];\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Longest Common Subsequence (LCS)\n\n### The Problem\n\nFind the longest sequence present in both strings (not necessarily contiguous).\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ LCS VISUALIZATION │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ String A: A B C D G H │\n│ String B: A E D F H R │\n│ │\n│ LCS: A D H (length = 3) │\n│ ↑ ↑ ↑ │\n│ │\n│ State: dp[i][j] = LCS length for A[0..i-1] and B[0..j-1] │\n│ │\n│ Transition: │\n│ if A[i-1] == B[j-1]: │\n│ dp[i][j] = dp[i-1][j-1] + 1 // Match! Extend LCS │\n│ else: │\n│ dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // Skip one char │\n│ │\n│ \"\" A E D F H R │\n│ \"\" 0 0 0 0 0 0 0 │\n│ A 0 1 1 1 1 1 1 │\n│ B 0 1 1 1 1 1 1 │\n│ C 0 1 1 1 1 1 1 │\n│ D 0 1 1 2 2 2 2 │\n│ G 0 1 1 2 2 2 2 │\n│ H 0 1 1 2 2 3 3 ← Answer │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Implementation\n\n```java\npublic class LCS {\n // Basic LCS - O(nm) time and space\n public int lcs(String a, String b) {\n int n = a.length(), m = b.length();\n int[][] dp = new int[n + 1][m + 1];\n\n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= m; j++) {\n if (a.charAt(i - 1) == b.charAt(j - 1)) {\n dp[i][j] = dp[i - 1][j - 1] + 1;\n } else {\n dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);\n }\n }\n }\n\n return dp[n][m];\n }\n\n // Space-optimized - O(min(n,m)) space\n public int lcsOptimized(String a, String b) {\n // Make b the shorter string\n if (a.length() < b.length()) {\n String temp = a; a = b; b = temp;\n }\n\n int[] prev = new int[b.length() + 1];\n int[] curr = new int[b.length() + 1];\n\n for (int i = 1; i <= a.length(); i++) {\n for (int j = 1; j <= b.length(); j++) {\n if (a.charAt(i - 1) == b.charAt(j - 1)) {\n curr[j] = prev[j - 1] + 1;\n } else {\n curr[j] = Math.max(prev[j], curr[j - 1]);\n }\n }\n int[] temp = prev;\n prev = curr;\n curr = temp;\n }\n\n return prev[b.length()];\n }\n\n // Get actual LCS string\n public String lcsString(String a, String b) {\n int n = a.length(), m = b.length();\n int[][] dp = new int[n + 1][m + 1];\n\n // Fill DP table\n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= m; j++) {\n if (a.charAt(i - 1) == b.charAt(j - 1)) {\n dp[i][j] = dp[i - 1][j - 1] + 1;\n } else {\n dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);\n }\n }\n }\n\n // Backtrack to build LCS\n StringBuilder lcs = new StringBuilder();\n int i = n, j = m;\n while (i > 0 && j > 0) {\n if (a.charAt(i - 1) == b.charAt(j - 1)) {\n lcs.append(a.charAt(i - 1));\n i--; j--;\n } else if (dp[i - 1][j] > dp[i][j - 1]) {\n i--;\n } else {\n j--;\n }\n }\n\n return lcs.reverse().toString();\n }\n}\n```\n\n### LCS Variants\n\n```java\npublic class LCSVariants {\n // Longest Common Substring (must be contiguous)\n public int longestCommonSubstring(String a, String b) {\n int n = a.length(), m = b.length();\n int[][] dp = new int[n + 1][m + 1];\n int maxLen = 0;\n\n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= m; j++) {\n if (a.charAt(i - 1) == b.charAt(j - 1)) {\n dp[i][j] = dp[i - 1][j - 1] + 1;\n maxLen = Math.max(maxLen, dp[i][j]);\n }\n // else dp[i][j] = 0 (implicit)\n }\n }\n\n return maxLen;\n }\n\n // Shortest Common Supersequence\n public int scs(String a, String b) {\n int lcsLen = new LCS().lcs(a, b);\n // SCS = a + b - LCS\n return a.length() + b.length() - lcsLen;\n }\n\n // Longest Palindromic Subsequence\n public int longestPalindromeSubseq(String s) {\n // LPS(s) = LCS(s, reverse(s))\n String reversed = new StringBuilder(s).reverse().toString();\n return new LCS().lcs(s, reversed);\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Longest Increasing Subsequence (LIS)\n\n### The Problem\n\nFind the longest strictly increasing subsequence.\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ LIS EXAMPLE │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Array: [10, 9, 2, 5, 3, 7, 101, 18] │\n│ │\n│ LIS: [ 2, 3, 7, 18] (length = 4) │\n│ or: [ 2, 5, 7, 18] (also length 4) │\n│ │\n│ O(n²) DP State: │\n│ dp[i] = LIS length ending at index i │\n│ │\n│ Transition: │\n│ dp[i] = 1 + max(dp[j]) for all j < i where arr[j] < arr[i] │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### O(n²) Implementation\n\n```java\npublic class LIS {\n // O(n²) DP solution\n public int lisDP(int[] nums) {\n if (nums.length == 0) return 0;\n\n int[] dp = new int[nums.length];\n Arrays.fill(dp, 1); // Each element is LIS of length 1\n int maxLen = 1;\n\n for (int i = 1; i < nums.length; i++) {\n for (int j = 0; j < i; j++) {\n if (nums[j] < nums[i]) {\n dp[i] = Math.max(dp[i], dp[j] + 1);\n }\n }\n maxLen = Math.max(maxLen, dp[i]);\n }\n\n return maxLen;\n }\n}\n```\n\n### O(n log n) Binary Search Solution\n\n```java\npublic class LISOptimized {\n // O(n log n) using binary search\n public int lis(int[] nums) {\n // tails[i] = smallest ending element of LIS of length i+1\n int[] tails = new int[nums.length];\n int size = 0;\n\n for (int num : nums) {\n // Binary search: find first tail >= num\n int left = 0, right = size;\n while (left < right) {\n int mid = left + (right - left) / 2;\n if (tails[mid] < num) {\n left = mid + 1;\n } else {\n right = mid;\n }\n }\n\n // Update tails\n tails[left] = num;\n if (left == size) {\n size++; // Extended LIS\n }\n }\n\n return size;\n }\n\n // Get actual LIS sequence\n public int[] lisSequence(int[] nums) {\n int n = nums.length;\n int[] tails = new int[n];\n int[] tailIndices = new int[n]; // Index in nums for each tail\n int[] prev = new int[n]; // Previous element index in LIS\n Arrays.fill(prev, -1);\n int size = 0;\n\n for (int i = 0; i < n; i++) {\n int left = 0, right = size;\n while (left < right) {\n int mid = left + (right - left) / 2;\n if (tails[mid] < nums[i]) {\n left = mid + 1;\n } else {\n right = mid;\n }\n }\n\n tails[left] = nums[i];\n tailIndices[left] = i;\n\n if (left > 0) {\n prev[i] = tailIndices[left - 1];\n }\n\n if (left == size) size++;\n }\n\n // Reconstruct sequence\n int[] lis = new int[size];\n int idx = tailIndices[size - 1];\n for (int i = size - 1; i >= 0; i--) {\n lis[i] = nums[idx];\n idx = prev[idx];\n }\n\n return lis;\n }\n}\n```\n\n### LIS Variants\n\n```java\npublic class LISVariants {\n // Longest Non-Decreasing Subsequence (allows equal)\n public int lnds(int[] nums) {\n int[] tails = new int[nums.length];\n int size = 0;\n\n for (int num : nums) {\n // Use upper_bound instead of lower_bound\n int left = 0, right = size;\n while (left < right) {\n int mid = left + (right - left) / 2;\n if (tails[mid] <= num) { // <= instead of <\n left = mid + 1;\n } else {\n right = mid;\n }\n }\n tails[left] = num;\n if (left == size) size++;\n }\n\n return size;\n }\n\n // Longest Bitonic Subsequence (increases then decreases)\n public int longestBitonic(int[] nums) {\n int n = nums.length;\n int[] lisLeft = new int[n]; // LIS ending at i\n int[] lisRight = new int[n]; // LIS starting at i (reversed)\n\n // Compute LIS from left\n Arrays.fill(lisLeft, 1);\n for (int i = 1; i < n; i++) {\n for (int j = 0; j < i; j++) {\n if (nums[j] < nums[i]) {\n lisLeft[i] = Math.max(lisLeft[i], lisLeft[j] + 1);\n }\n }\n }\n\n // Compute LIS from right\n Arrays.fill(lisRight, 1);\n for (int i = n - 2; i >= 0; i--) {\n for (int j = n - 1; j > i; j--) {\n if (nums[j] < nums[i]) {\n lisRight[i] = Math.max(lisRight[i], lisRight[j] + 1);\n }\n }\n }\n\n // Find maximum bitonic\n int maxLen = 0;\n for (int i = 0; i < n; i++) {\n maxLen = Math.max(maxLen, lisLeft[i] + lisRight[i] - 1);\n }\n\n return maxLen;\n }\n\n // Number of LIS (count all LIS of maximum length)\n public int numberOfLIS(int[] nums) {\n int n = nums.length;\n int[] length = new int[n]; // LIS length ending at i\n int[] count = new int[n]; // Number of LIS ending at i\n Arrays.fill(length, 1);\n Arrays.fill(count, 1);\n\n int maxLen = 1;\n\n for (int i = 1; i < n; i++) {\n for (int j = 0; j < i; j++) {\n if (nums[j] < nums[i]) {\n if (length[j] + 1 > length[i]) {\n length[i] = length[j] + 1;\n count[i] = count[j];\n } else if (length[j] + 1 == length[i]) {\n count[i] += count[j];\n }\n }\n }\n maxLen = Math.max(maxLen, length[i]);\n }\n\n int totalCount = 0;\n for (int i = 0; i < n; i++) {\n if (length[i] == maxLen) {\n totalCount += count[i];\n }\n }\n\n return totalCount;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Edit Distance (Levenshtein)\n\n### The Problem\n\nMinimum operations to transform one string to another.\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ EDIT DISTANCE │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Transform \"horse\" → \"ros\" │\n│ │\n│ Operations: │\n│ horse → rorse (replace 'h' with 'r') │\n│ rorse → rose (delete 'r') │\n│ rose → ros (delete 'e') │\n│ │\n│ Edit distance = 3 │\n│ │\n│ State: dp[i][j] = edit distance for s1[0..i-1] and s2[0..j-1] │\n│ │\n│ Transition: │\n│ if s1[i-1] == s2[j-1]: │\n│ dp[i][j] = dp[i-1][j-1] // No operation needed │\n│ else: │\n│ dp[i][j] = 1 + min( │\n│ dp[i-1][j-1], // Replace │\n│ dp[i-1][j], // Delete from s1 │\n│ dp[i][j-1] // Insert into s1 │\n│ ) │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Implementation\n\n```java\npublic class EditDistance {\n // Basic edit distance - O(nm) time and space\n public int minDistance(String s1, String s2) {\n int n = s1.length(), m = s2.length();\n int[][] dp = new int[n + 1][m + 1];\n\n // Base cases: converting to/from empty string\n for (int i = 0; i <= n; i++) dp[i][0] = i; // Delete all\n for (int j = 0; j <= m; j++) dp[0][j] = j; // Insert all\n\n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= m; j++) {\n if (s1.charAt(i - 1) == s2.charAt(j - 1)) {\n dp[i][j] = dp[i - 1][j - 1];\n } else {\n dp[i][j] = 1 + Math.min(\n dp[i - 1][j - 1], // Replace\n Math.min(\n dp[i - 1][j], // Delete\n dp[i][j - 1] // Insert\n )\n );\n }\n }\n }\n\n return dp[n][m];\n }\n\n // Space-optimized - O(min(n,m)) space\n public int minDistanceOptimized(String s1, String s2) {\n if (s1.length() < s2.length()) {\n String temp = s1; s1 = s2; s2 = temp;\n }\n\n int[] prev = new int[s2.length() + 1];\n int[] curr = new int[s2.length() + 1];\n\n for (int j = 0; j <= s2.length(); j++) prev[j] = j;\n\n for (int i = 1; i <= s1.length(); i++) {\n curr[0] = i;\n for (int j = 1; j <= s2.length(); j++) {\n if (s1.charAt(i - 1) == s2.charAt(j - 1)) {\n curr[j] = prev[j - 1];\n } else {\n curr[j] = 1 + Math.min(prev[j - 1],\n Math.min(prev[j], curr[j - 1]));\n }\n }\n int[] temp = prev; prev = curr; curr = temp;\n }\n\n return prev[s2.length()];\n }\n\n // Get actual edit operations\n public List getOperations(String s1, String s2) {\n int n = s1.length(), m = s2.length();\n int[][] dp = new int[n + 1][m + 1];\n\n for (int i = 0; i <= n; i++) dp[i][0] = i;\n for (int j = 0; j <= m; j++) dp[0][j] = j;\n\n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= m; j++) {\n if (s1.charAt(i - 1) == s2.charAt(j - 1)) {\n dp[i][j] = dp[i - 1][j - 1];\n } else {\n dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],\n Math.min(dp[i - 1][j], dp[i][j - 1]));\n }\n }\n }\n\n // Backtrack to find operations\n List ops = new ArrayList<>();\n int i = n, j = m;\n while (i > 0 || j > 0) {\n if (i > 0 && j > 0 && s1.charAt(i - 1) == s2.charAt(j - 1)) {\n i--; j--;\n } else if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + 1) {\n ops.add(\"Replace \" + s1.charAt(i - 1) + \" with \" + s2.charAt(j - 1));\n i--; j--;\n } else if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {\n ops.add(\"Delete \" + s1.charAt(i - 1));\n i--;\n } else {\n ops.add(\"Insert \" + s2.charAt(j - 1));\n j--;\n }\n }\n\n Collections.reverse(ops);\n return ops;\n }\n}\n```\n\n### Edit Distance Variants\n\n```java\npublic class EditDistanceVariants {\n // With different operation costs\n public int weightedEditDistance(String s1, String s2,\n int insertCost, int deleteCost, int replaceCost) {\n int n = s1.length(), m = s2.length();\n int[][] dp = new int[n + 1][m + 1];\n\n for (int i = 0; i <= n; i++) dp[i][0] = i * deleteCost;\n for (int j = 0; j <= m; j++) dp[0][j] = j * insertCost;\n\n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= m; j++) {\n if (s1.charAt(i - 1) == s2.charAt(j - 1)) {\n dp[i][j] = dp[i - 1][j - 1];\n } else {\n dp[i][j] = Math.min(\n dp[i - 1][j - 1] + replaceCost,\n Math.min(\n dp[i - 1][j] + deleteCost,\n dp[i][j - 1] + insertCost\n )\n );\n }\n }\n }\n\n return dp[n][m];\n }\n\n // One edit distance - check if exactly one operation needed\n public boolean isOneEditDistance(String s, String t) {\n int n = s.length(), m = t.length();\n if (Math.abs(n - m) > 1) return false;\n\n if (n > m) {\n String temp = s; s = t; t = temp;\n int tempLen = n; n = m; m = tempLen;\n }\n\n int i = 0, j = 0;\n boolean foundDiff = false;\n\n while (i < n && j < m) {\n if (s.charAt(i) != t.charAt(j)) {\n if (foundDiff) return false;\n foundDiff = true;\n if (n == m) i++; // Replace\n // else: Insert (just advance j)\n } else {\n i++;\n }\n j++;\n }\n\n return foundDiff || (i == n && j == m - 1);\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Matrix Chain Multiplication\n\n### The Problem\n\nFind the optimal way to parenthesize matrix multiplication to minimize operations.\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ MATRIX CHAIN MULTIPLICATION │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Matrices: A(10×30) × B(30×5) × C(5×60) │\n│ │\n│ Option 1: (A × B) × C │\n│ A × B = 10×30×5 = 1500 ops → result 10×5 │\n│ (AB) × C = 10×5×60 = 3000 ops │\n│ Total: 4500 ops │\n│ │\n│ Option 2: A × (B × C) │\n│ B × C = 30×5×60 = 9000 ops → result 30×60 │\n│ A × (BC) = 10×30×60 = 18000 ops │\n│ Total: 27000 ops │\n│ │\n│ Optimal: Option 1 (6× faster!) │\n│ │\n│ State: dp[i][j] = min cost to multiply matrices i to j │\n│ │\n│ Transition: │\n│ dp[i][j] = min over k of: │\n│ dp[i][k] + dp[k+1][j] + dims[i-1] × dims[k] × dims[j] │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Implementation\n\n```java\npublic class MatrixChainMultiplication {\n // dims[i-1] × dims[i] is dimensions of matrix i\n // e.g., dims = [10, 30, 5, 60] means A(10×30), B(30×5), C(5×60)\n\n public int matrixChainOrder(int[] dims) {\n int n = dims.length - 1; // Number of matrices\n int[][] dp = new int[n][n];\n\n // Length of chain (from 2 to n)\n for (int len = 2; len <= n; len++) {\n for (int i = 0; i <= n - len; i++) {\n int j = i + len - 1;\n dp[i][j] = Integer.MAX_VALUE;\n\n // Try all split points\n for (int k = i; k < j; k++) {\n int cost = dp[i][k] + dp[k + 1][j]\n + dims[i] * dims[k + 1] * dims[j + 1];\n dp[i][j] = Math.min(dp[i][j], cost);\n }\n }\n }\n\n return dp[0][n - 1];\n }\n\n // Get optimal parenthesization\n public String optimalParenthesization(int[] dims) {\n int n = dims.length - 1;\n int[][] dp = new int[n][n];\n int[][] split = new int[n][n]; // Track where to split\n\n for (int len = 2; len <= n; len++) {\n for (int i = 0; i <= n - len; i++) {\n int j = i + len - 1;\n dp[i][j] = Integer.MAX_VALUE;\n\n for (int k = i; k < j; k++) {\n int cost = dp[i][k] + dp[k + 1][j]\n + dims[i] * dims[k + 1] * dims[j + 1];\n if (cost < dp[i][j]) {\n dp[i][j] = cost;\n split[i][j] = k;\n }\n }\n }\n }\n\n return buildParenthesization(split, 0, n - 1);\n }\n\n private String buildParenthesization(int[][] split, int i, int j) {\n if (i == j) {\n return \"M\" + i;\n }\n return \"(\" + buildParenthesization(split, i, split[i][j])\n + \" × \" + buildParenthesization(split, split[i][j] + 1, j) + \")\";\n }\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Knapsack Wrong Direction\n\n```java\n// ❌ WRONG: Left to right allows reusing same item (unbounded)\nfor (int i = 0; i < n; i++) {\n for (int w = weights[i]; w <= capacity; w++) {\n dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);\n }\n}\n\n// ✅ CORRECT: Right to left for 0/1 knapsack\nfor (int i = 0; i < n; i++) {\n for (int w = capacity; w >= weights[i]; w--) {\n dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);\n }\n}\n```\n\n---\n\n### Mistake 2: LCS Off-by-One\n\n```java\n// ❌ WRONG: Using 0-indexed when dp is 1-indexed\nif (a.charAt(i) == b.charAt(j)) { // Should be i-1, j-1\n dp[i][j] = dp[i-1][j-1] + 1;\n}\n\n// ✅ CORRECT: Match indices properly\nif (a.charAt(i - 1) == b.charAt(j - 1)) {\n dp[i][j] = dp[i - 1][j - 1] + 1;\n}\n```\n\n---\n\n### Mistake 3: Edit Distance Missing Base Cases\n\n```java\n// ❌ WRONG: Missing initialization\nint[][] dp = new int[n + 1][m + 1];\n// dp[i][0] and dp[0][j] are 0 by default - WRONG!\n\n// ✅ CORRECT: Initialize base cases\nfor (int i = 0; i <= n; i++) dp[i][0] = i;\nfor (int j = 0; j <= m; j++) dp[0][j] = j;\n```\n\n---\n\n## 🐛 Debug This: LIS Binary Search Bug\n\nThis O(n log n) LIS implementation has a bug. Can you find it?\n\n```java\npublic int lis(int[] nums) {\n int[] tails = new int[nums.length];\n int size = 0;\n\n for (int num : nums) {\n int left = 0, right = size;\n while (left < right) {\n int mid = left + (right - left) / 2;\n // BUG IS HERE\n if (tails[mid] <= num) {\n left = mid + 1;\n } else {\n right = mid;\n }\n }\n\n tails[left] = num;\n if (left == size) size++;\n }\n\n return size;\n}\n```\n\n

🔍 Click to reveal the bug

\n\n**Bug**: Using `<=` instead of `<` in comparison.\n\n```java\n// ❌ BUG: <= finds longest NON-DECREASING subsequence\nif (tails[mid] <= num) {\n\n// ✅ FIX: < for strictly increasing subsequence\nif (tails[mid] < num) {\n```\n\nWith `<=`, equal elements are placed after existing elements, allowing duplicates in the subsequence. For strictly increasing LIS, we need `<`.\n\n**Example**:\n```\nInput: [1, 3, 3, 5]\nBug answer: 4 (allows [1, 3, 3, 5])\nCorrect: 3 ([1, 3, 5])\n```\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Target Sum ⭐⭐\n\nGiven array and target, assign + or - to each element to reach target. Count ways.\n\n```java\npublic int findTargetSumWays(int[] nums, int target) {\n // Hint: Transform to subset sum problem\n}\n```\n\n---\n\n### Exercise 2: Longest Palindromic Substring ⭐⭐\n\nFind the longest palindromic substring (contiguous).\n\n```java\npublic String longestPalindrome(String s) {\n // dp[i][j] = true if s[i..j] is palindrome\n}\n```\n\n---\n\n### Exercise 3: Distinct Subsequences ⭐⭐⭐\n\nCount distinct subsequences of s that equal t.\n\n```java\npublic int numDistinct(String s, String t) {\n // Similar to LCS but counting\n}\n```\n\n---\n\n### Exercise 4: Interleaving String ⭐⭐⭐\n\nCheck if s3 is formed by interleaving s1 and s2.\n\n```java\npublic boolean isInterleave(String s1, String s2, String s3) {\n // dp[i][j] = true if s3[0..i+j-1] is interleaving of s1[0..i-1] and s2[0..j-1]\n}\n```\n\n---\n\n### Exercise 5: Burst Balloons ⭐⭐⭐⭐\n\nBurst balloons to maximize coins (similar to matrix chain).\n\n```java\npublic int maxCoins(int[] nums) {\n // dp[i][j] = max coins for bursting balloons i to j\n // Think: which balloon to burst LAST in range [i,j]\n}\n```\n\n---\n\n## 🎤 Interview Questions\n\n### Q1: \"Explain the difference between LCS and LIS.\"\n\n**Answer**:\n\n| Aspect | LCS | LIS |\n|--------|-----|-----|\n| Input | Two sequences | One sequence |\n| Goal | Longest common to both | Longest increasing |\n| State | dp[i][j] - 2D | dp[i] - 1D |\n| Time | O(nm) | O(n²) or O(n log n) |\n| Application | Diff, DNA alignment | Patience sorting |\n\n**Key insight**: LCS finds matching elements between sequences; LIS finds ordered elements within one sequence.\n\n---\n\n### Q2: \"How would you optimize 0/1 Knapsack for very large capacity?\"\n\n**Answer**: Several approaches depending on constraints:\n\n1. **Meet in the middle** (if n ≤ 40):\n - Split items into two halves\n - Enumerate all 2^(n/2) combinations for each\n - Use binary search to find best complement\n - O(2^(n/2) × n) instead of O(nW)\n\n2. **If values are small** (sum of values ≤ V):\n - dp[v] = minimum weight to achieve value v\n - O(nV) instead of O(nW)\n\n3. **Sparse DP** (if few distinct weights):\n - Use HashMap instead of array\n - Only store reachable states\n\n---\n\n### Q3: \"When would edit distance give wrong results for spell checking?\"\n\n**Answer**: Edit distance has limitations:\n\n1. **Doesn't consider keyboard layout**:\n - \"teh\" → \"the\" (2 edits)\n - But they're adjacent keys - should be weighted lower\n\n2. **Ignores phonetics**:\n - \"knight\" vs \"nite\" (4 edits)\n - But they sound the same\n\n3. **Equal cost for all operations**:\n - Transposition (\"hte\" → \"the\") costs 2 but is a common typo\n\n**Better approaches**:\n- Damerau-Levenshtein (adds transposition)\n- Weighted edit distance (keyboard-aware)\n- Soundex/Metaphone (phonetic matching)\n\n---\n\n### Q4: \"How is LIS related to patience sorting?\"\n\n**Answer**: The O(n log n) LIS algorithm is essentially patience sorting:\n\n```\nPatience sorting:\n- Deal cards into piles\n- Each pile is descending\n- Place card on leftmost pile where it fits\n- Number of piles = LIS length\n\nLIS algorithm:\n- tails[i] = smallest ending element of LIS length i+1\n- Binary search to find where new element goes\n- Same as finding which pile to place card\n\nThis connection shows:\n1. LIS can be found in O(n log n)\n2. Patience sorting produces an optimal LIS\n3. The algorithm is actually a greedy approach\n```\n\n---\n\n### Q5: \"How would you find all LCS strings, not just length?\"\n\n**Answer**:\n\n```java\npublic Set allLCS(String a, String b) {\n int n = a.length(), m = b.length();\n int[][] dp = new int[n + 1][m + 1];\n\n // Fill dp table (standard LCS)\n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= m; j++) {\n if (a.charAt(i - 1) == b.charAt(j - 1)) {\n dp[i][j] = dp[i - 1][j - 1] + 1;\n } else {\n dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);\n }\n }\n }\n\n // Backtrack to find all LCS\n return backtrackAll(dp, a, b, n, m);\n}\n\nprivate Set backtrackAll(int[][] dp, String a, String b, int i, int j) {\n if (i == 0 || j == 0) {\n return new HashSet<>(Collections.singleton(\"\"));\n }\n\n if (a.charAt(i - 1) == b.charAt(j - 1)) {\n Set result = new HashSet<>();\n for (String s : backtrackAll(dp, a, b, i - 1, j - 1)) {\n result.add(s + a.charAt(i - 1));\n }\n return result;\n }\n\n Set result = new HashSet<>();\n if (dp[i - 1][j] >= dp[i][j - 1]) {\n result.addAll(backtrackAll(dp, a, b, i - 1, j));\n }\n if (dp[i][j - 1] >= dp[i - 1][j]) {\n result.addAll(backtrackAll(dp, a, b, i, j - 1));\n }\n return result;\n}\n```\n\n**Caution**: Can be exponential in number of LCS strings!\n\n---\n\n## 📋 Quick Reference\n\n### Pattern Recognition\n\n| Problem Type | State | Transition |\n|--------------|-------|------------|\n| 0/1 Knapsack | dp[i][w] | max(skip, take) |\n| Unbounded Knapsack | dp[w] | max over all items |\n| LCS | dp[i][j] | match or max(skip) |\n| LIS | dp[i] | max(dp[j]+1) for j= weight[i]; w--)\n\n// Knapsack (unbounded): left to right\nfor (int w = weight[i]; w <= W; w++)\n\n// LCS/Edit: 2D or rolling array\ndp[i][j] depends on dp[i-1][j-1], dp[i-1][j], dp[i][j-1]\n\n// LIS: binary search on tails\nint pos = Arrays.binarySearch(tails, 0, size, num);\n```\n\n---\n\n## 🔗 What's Next?\n\nIn **Part 18: Advanced DP Techniques**, we'll explore:\n- DP on trees\n- Bitmask DP\n- Digit DP\n- Convex hull trick\n- Space optimization techniques\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| 0 | Full read + Knapsack exercise | 90 min |\n| 1 | Quick Reference | 10 min |\n| 3 | Implement LCS from memory | 20 min |\n| 7 | LIS + Edit Distance exercises | 30 min |\n| 14 | Debug exercise + Matrix Chain | 20 min |\n| 30 | All interview questions | 15 min |\n\n---\n\n**Next**: [Part 18: Advanced DP Techniques →](./algorithms-part-18-advanced-dp-techniques.md)\n\n**Series**: [Algorithms Compendium Index](./algorithms-part-0-series-overview.md)\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.269307Z","createdAt","2026-06-10T07:19:25.270192Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",25,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",17,"author",{"_31":55,"_103":57,"_104":105,"_106":107,"_108":-5,"_109":-5,"_110":-5,"_111":-5,"_112":-5},"category",{"_31":99,"_73":59,"_35":100,"_76":101,"_102":-5},"tags",[79,80,81,82,83],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":96,"_73":97,"_35":98},{"_31":93,"_73":94,"_35":95},{"_31":90,"_73":91,"_35":92},{"_31":87,"_73":88,"_35":89},{"_31":84,"_73":85,"_35":86},191,"Matrix Chain","matrix-chain",189,"Lis","lis",188,"Lcs","lcs",187,"Knapsack","knapsack",190,"Edit Distance","edit-distance",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]