[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":83,"_73":84,"_35":85},"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",45,"title","Advanced DP Techniques","slug","algorithms-part-18-advanced-dp-techniques","excerpt","Apply tree DP, bitmask DP for small state spaces, digit DP for number properties, and optimization techniques like convex hull trick.","# Part 18: Advanced DP Techniques - Trees, Bitmasks, and Optimizations\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Time to Read | 40 minutes |\n| Prerequisites | Parts 16-17 (DP Foundations and Classic Patterns) |\n| Key Concepts | Tree DP, Bitmask DP, Digit DP, Optimization Techniques |\n| Difficulty | ⭐⭐⭐⭐ (Advanced) |\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ ADVANCED DP TECHNIQUES │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ TREE DP BITMASK DP │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ 1 │ │ Subset: 1011 │ │\n│ │ /|\\ │ │ = {0, 1, 3} │ │\n│ │ 2 3 4 │ │ │ │\n│ │ /| │ │ TSP: visit all │ │\n│ │ 5 6 │ │ cities exactly │ │\n│ │ │ │ once │ │\n│ │ dp[node] from │ │ │ │\n│ │ children │ │ dp[mask][last] │ │\n│ └─────────────────┘ └─────────────────┘ │\n│ │\n│ DIGIT DP OPTIMIZATIONS │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ Count numbers │ │ • Convex Hull │ │\n│ │ with property │ │ Trick │ │\n│ │ in range [L,R] │ │ │ │\n│ │ │ │ • Divide & │ │\n│ │ dp[pos][state] │ │ Conquer Opt │ │\n│ │ [tight][started]│ │ │ │\n│ │ │ │ • Knuth's Opt │ │\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 tree problems**: Apply DP on tree structures\n2. **Use bitmask DP**: Solve problems with small state spaces\n3. **Apply digit DP**: Count numbers with specific properties\n4. **Optimize transitions**: Use convex hull trick and other optimizations\n5. **Reduce space complexity**: Rolling arrays and state compression\n\n---\n\n## 🔥 Production Story: The Delivery Route Optimizer\n\nA delivery company needed to optimize routes for drivers visiting multiple locations daily.\n\n### The Problem\n\n```java\n// ❌ Brute force - checking all permutations\npublic class NaiveTSP {\n public int shortestRoute(int[][] distances, int n) {\n int[] cities = new int[n];\n for (int i = 0; i < n; i++) cities[i] = i;\n\n int minDist = Integer.MAX_VALUE;\n // Try all n! permutations - EXPONENTIAL\n do {\n int dist = calculateRoute(distances, cities);\n minDist = Math.min(minDist, dist);\n } while (nextPermutation(cities));\n\n return minDist;\n }\n // 20 cities: 20! = 2.4 × 10^18 permutations - IMPOSSIBLE\n}\n```\n\n### The Solution: Bitmask DP\n\n```java\n// ✅ Bitmask DP - O(n² × 2^n)\npublic class TSPBitmask {\n public int shortestRoute(int[][] dist, int n) {\n int[][] dp = new int[1 << n][n];\n for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);\n\n // Start from city 0\n dp[1][0] = 0;\n\n for (int mask = 1; mask < (1 << n); mask++) {\n for (int last = 0; last < n; last++) {\n if ((mask & (1 << last)) == 0) continue;\n if (dp[mask][last] == Integer.MAX_VALUE) continue;\n\n // Try going to next unvisited city\n for (int next = 0; next < n; next++) {\n if ((mask & (1 << next)) != 0) continue;\n\n int newMask = mask | (1 << next);\n dp[newMask][next] = Math.min(\n dp[newMask][next],\n dp[mask][last] + dist[last][next]\n );\n }\n }\n }\n\n // Return to start\n int allVisited = (1 << n) - 1;\n int minDist = Integer.MAX_VALUE;\n for (int last = 1; last < n; last++) {\n if (dp[allVisited][last] != Integer.MAX_VALUE) {\n minDist = Math.min(minDist, dp[allVisited][last] + dist[last][0]);\n }\n }\n\n return minDist;\n }\n}\n```\n\n### The Impact\n\n| Cities | Brute Force | Bitmask DP |\n|--------|-------------|------------|\n| 10 | 3.6M ops | 10K ops |\n| 15 | 1.3T ops | 7.4M ops |\n| 20 | Impossible | 419M ops |\n| 25 | Impossible | ~26B ops (feasible) |\n\n---\n\n## 🔬 Deep Dive: DP on Trees\n\n### The Concept\n\nTree DP computes solutions bottom-up from leaves to root.\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ TREE DP PATTERN │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ 1 (root) │\n│ /|\\ │\n│ 2 3 4 Process order: 5,6,2,3,4,1 │\n│ /| (post-order: children before parent) │\n│ 5 6 │\n│ │\n│ Pattern: │\n│ void dfs(int node, int parent) { │\n│ for (int child : adj[node]) { │\n│ if (child != parent) { │\n│ dfs(child, node); │\n│ // Combine child's DP into node's DP │\n│ } │\n│ } │\n│ // Compute dp[node] from dp[children] │\n│ } │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Example: Maximum Independent Set in Tree\n\n```java\npublic class TreeDP {\n private List> adj;\n private int[] values;\n private int[][] dp; // dp[node][0/1] = max value if node not/taken\n\n public int maxIndependentSet(int[] values, int[][] edges) {\n int n = values.length;\n this.values = values;\n this.adj = new ArrayList<>();\n this.dp = new int[n][2];\n\n for (int i = 0; i < n; i++) adj.add(new ArrayList<>());\n for (int[] e : edges) {\n adj.get(e[0]).add(e[1]);\n adj.get(e[1]).add(e[0]);\n }\n\n dfs(0, -1);\n return Math.max(dp[0][0], dp[0][1]);\n }\n\n private void dfs(int node, int parent) {\n dp[node][0] = 0; // Don't take this node\n dp[node][1] = values[node]; // Take this node\n\n for (int child : adj.get(node)) {\n if (child == parent) continue;\n dfs(child, node);\n\n // If we don't take node, children can be taken or not\n dp[node][0] += Math.max(dp[child][0], dp[child][1]);\n\n // If we take node, children cannot be taken\n dp[node][1] += dp[child][0];\n }\n }\n}\n```\n\n### Tree Diameter\n\n```java\npublic class TreeDiameter {\n private List> adj;\n private int diameter = 0;\n\n public int treeDiameter(int n, int[][] edges) {\n adj = new ArrayList<>();\n for (int i = 0; i < n; i++) adj.add(new ArrayList<>());\n for (int[] e : edges) {\n adj.get(e[0]).add(e[1]);\n adj.get(e[1]).add(e[0]);\n }\n\n dfs(0, -1);\n return diameter;\n }\n\n // Returns max depth from this node\n private int dfs(int node, int parent) {\n int max1 = 0, max2 = 0; // Two longest paths through children\n\n for (int child : adj.get(node)) {\n if (child == parent) continue;\n int childDepth = dfs(child, node) + 1;\n\n if (childDepth > max1) {\n max2 = max1;\n max1 = childDepth;\n } else if (childDepth > max2) {\n max2 = childDepth;\n }\n }\n\n // Diameter through this node = max1 + max2\n diameter = Math.max(diameter, max1 + max2);\n\n return max1;\n }\n}\n```\n\n### Tree DP with Rerooting\n\nFor problems where we need the answer for each node as root:\n\n```java\npublic class RerootingDP {\n // Example: Sum of distances from each node to all other nodes\n private List> adj;\n private int[] subtreeSize;\n private long[] subtreeSum; // Sum of distances in subtree\n private long[] answer; // Final answer for each node\n\n public long[] sumOfDistances(int n, int[][] edges) {\n adj = new ArrayList<>();\n for (int i = 0; i < n; i++) adj.add(new ArrayList<>());\n for (int[] e : edges) {\n adj.get(e[0]).add(e[1]);\n adj.get(e[1]).add(e[0]);\n }\n\n subtreeSize = new int[n];\n subtreeSum = new long[n];\n answer = new long[n];\n\n // First DFS: compute subtree values rooted at 0\n dfs1(0, -1);\n\n // Second DFS: reroot to compute answer for all nodes\n dfs2(0, -1, n);\n\n return answer;\n }\n\n private void dfs1(int node, int parent) {\n subtreeSize[node] = 1;\n subtreeSum[node] = 0;\n\n for (int child : adj.get(node)) {\n if (child == parent) continue;\n dfs1(child, node);\n subtreeSize[node] += subtreeSize[child];\n subtreeSum[node] += subtreeSum[child] + subtreeSize[child];\n }\n }\n\n private void dfs2(int node, int parent, int n) {\n answer[node] = subtreeSum[node];\n\n for (int child : adj.get(node)) {\n if (child == parent) continue;\n\n // Temporarily reroot: make child the root\n long oldChildSum = subtreeSum[child];\n int oldChildSize = subtreeSize[child];\n\n // Remove child's contribution from node\n subtreeSum[node] -= subtreeSum[child] + subtreeSize[child];\n subtreeSize[node] -= subtreeSize[child];\n\n // Add node's contribution to child\n subtreeSum[child] += subtreeSum[node] + subtreeSize[node];\n subtreeSize[child] += subtreeSize[node];\n\n dfs2(child, node, n);\n\n // Restore\n subtreeSize[child] = oldChildSize;\n subtreeSum[child] = oldChildSum;\n subtreeSize[node] += subtreeSize[child];\n subtreeSum[node] += subtreeSum[child] + subtreeSize[child];\n }\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Bitmask DP\n\n### When to Use\n\n- Small number of elements (n ≤ 20-25)\n- Need to track which elements are \"selected\"\n- Subset-based state transitions\n\n### Bit Manipulation Essentials\n\n```java\npublic class BitManipulation {\n // Check if bit i is set\n boolean isSet(int mask, int i) {\n return (mask & (1 << i)) != 0;\n }\n\n // Set bit i\n int setBit(int mask, int i) {\n return mask | (1 << i);\n }\n\n // Clear bit i\n int clearBit(int mask, int i) {\n return mask & ~(1 << i);\n }\n\n // Toggle bit i\n int toggleBit(int mask, int i) {\n return mask ^ (1 << i);\n }\n\n // Count set bits\n int countBits(int mask) {\n return Integer.bitCount(mask);\n }\n\n // Iterate through all subsets of mask\n void iterateSubsets(int mask) {\n for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {\n // Process subset 'sub'\n }\n // Don't forget empty subset if needed\n }\n\n // Get lowest set bit\n int lowestBit(int mask) {\n return mask & (-mask);\n }\n}\n```\n\n### TSP (Traveling Salesman Problem)\n\n```java\npublic class TSP {\n public int solveTSP(int[][] dist) {\n int n = dist.length;\n int[][] dp = new int[1 << n][n];\n\n for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);\n dp[1][0] = 0; // Start at city 0, only city 0 visited\n\n for (int mask = 1; mask < (1 << n); mask++) {\n for (int last = 0; last < n; last++) {\n if ((mask & (1 << last)) == 0) continue;\n if (dp[mask][last] == Integer.MAX_VALUE) continue;\n\n for (int next = 0; next < n; next++) {\n if ((mask & (1 << next)) != 0) continue; // Already visited\n\n int newMask = mask | (1 << next);\n dp[newMask][next] = Math.min(\n dp[newMask][next],\n dp[mask][last] + dist[last][next]\n );\n }\n }\n }\n\n // Return to start\n int fullMask = (1 << n) - 1;\n int ans = Integer.MAX_VALUE;\n for (int last = 1; last < n; last++) {\n if (dp[fullMask][last] != Integer.MAX_VALUE) {\n ans = Math.min(ans, dp[fullMask][last] + dist[last][0]);\n }\n }\n\n return ans;\n }\n}\n```\n\n### Assignment Problem (Matching)\n\n```java\npublic class AssignmentProblem {\n // Assign n workers to n jobs, minimize total cost\n public int minCostAssignment(int[][] cost) {\n int n = cost.length;\n int[] dp = new int[1 << n];\n Arrays.fill(dp, Integer.MAX_VALUE);\n dp[0] = 0;\n\n for (int mask = 0; mask < (1 << n); mask++) {\n int worker = Integer.bitCount(mask); // Which worker we're assigning\n if (worker >= n) continue;\n if (dp[mask] == Integer.MAX_VALUE) continue;\n\n for (int job = 0; job < n; job++) {\n if ((mask & (1 << job)) != 0) continue; // Job taken\n\n int newMask = mask | (1 << job);\n dp[newMask] = Math.min(dp[newMask],\n dp[mask] + cost[worker][job]);\n }\n }\n\n return dp[(1 << n) - 1];\n }\n}\n```\n\n### Subset Sum with Exact Selection\n\n```java\npublic class SubsetExactK {\n // Count subsets of exactly k elements with sum = target\n public int countSubsets(int[] nums, int k, int target) {\n int n = nums.length;\n int count = 0;\n\n for (int mask = 0; mask < (1 << n); mask++) {\n if (Integer.bitCount(mask) != k) continue;\n\n int sum = 0;\n for (int i = 0; i < n; i++) {\n if ((mask & (1 << i)) != 0) {\n sum += nums[i];\n }\n }\n\n if (sum == target) count++;\n }\n\n return count;\n }\n\n // DP version: dp[mask] = sum of subset represented by mask\n public int countSubsetsDP(int[] nums, int k, int target) {\n int n = nums.length;\n int[] sum = new int[1 << n];\n\n for (int mask = 0; mask < (1 << n); mask++) {\n // Compute sum efficiently using previous results\n if (mask == 0) {\n sum[mask] = 0;\n } else {\n int lastBit = mask & (-mask);\n int idx = Integer.numberOfTrailingZeros(lastBit);\n sum[mask] = sum[mask ^ lastBit] + nums[idx];\n }\n }\n\n int count = 0;\n for (int mask = 0; mask < (1 << n); mask++) {\n if (Integer.bitCount(mask) == k && sum[mask] == target) {\n count++;\n }\n }\n\n return count;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Digit DP\n\n### The Concept\n\nCount numbers in range [L, R] with certain properties by processing digit by digit.\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ DIGIT DP PATTERN │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Count numbers from 0 to N with property P │\n│ │\n│ Example: N = 234, count numbers with digit sum ≤ 10 │\n│ │\n│ State: dp[pos][sum][tight][started] │\n│ - pos: current digit position │\n│ - sum: running digit sum │\n│ - tight: are we still bounded by N? │\n│ - started: have we placed a non-zero digit? │\n│ │\n│ For N = 234: │\n│ - If tight and pos=0, digit can be 0,1,2 (not 3+) │\n│ - If not tight, digit can be 0-9 │\n│ │\n│ To count [L, R]: count(R) - count(L-1) │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Count Numbers with Digit Sum ≤ K\n\n```java\npublic class DigitDP {\n private String num;\n private int[][][] memo;\n\n public int countDigitSum(int n, int maxSum) {\n num = String.valueOf(n);\n memo = new int[num.length()][maxSum + 1][2];\n for (int[][] arr : memo) {\n for (int[] row : arr) Arrays.fill(row, -1);\n }\n\n return solve(0, 0, 1);\n }\n\n // pos: current position\n // sum: current digit sum\n // tight: 1 if bounded by num, 0 otherwise\n private int solve(int pos, int sum, int tight) {\n if (pos == num.length()) {\n return 1; // Valid number formed\n }\n\n if (memo[pos][sum][tight] != -1) {\n return memo[pos][sum][tight];\n }\n\n int limit = tight == 1 ? (num.charAt(pos) - '0') : 9;\n int result = 0;\n\n for (int digit = 0; digit <= limit; digit++) {\n int newSum = sum + digit;\n // Prune: if sum already exceeds max\n if (newSum > memo[0].length - 1) continue;\n\n int newTight = (tight == 1 && digit == limit) ? 1 : 0;\n result += solve(pos + 1, newSum, newTight);\n }\n\n memo[pos][sum][tight] = result;\n return result;\n }\n\n // Count in range [L, R]\n public int countInRange(int L, int R, int maxSum) {\n return countDigitSum(R, maxSum) - countDigitSum(L - 1, maxSum);\n }\n}\n```\n\n### Count Numbers Without Digit 4\n\n```java\npublic class NoFourDigitDP {\n private String num;\n private int[][] memo;\n\n public int countWithoutFour(int n) {\n num = String.valueOf(n);\n memo = new int[num.length()][2];\n for (int[] row : memo) Arrays.fill(row, -1);\n\n return solve(0, 1) - 1; // Subtract 1 to exclude 0\n }\n\n private int solve(int pos, int tight) {\n if (pos == num.length()) return 1;\n if (memo[pos][tight] != -1) return memo[pos][tight];\n\n int limit = tight == 1 ? (num.charAt(pos) - '0') : 9;\n int result = 0;\n\n for (int digit = 0; digit <= limit; digit++) {\n if (digit == 4) continue; // Skip 4\n\n int newTight = (tight == 1 && digit == limit) ? 1 : 0;\n result += solve(pos + 1, newTight);\n }\n\n memo[pos][tight] = result;\n return result;\n }\n}\n```\n\n### Count Numbers with No Repeated Digits\n\n```java\npublic class NoRepeatedDigits {\n private String num;\n private int[][][] memo;\n\n public int countNumbersWithUniqueDigits(int n) {\n num = String.valueOf(n);\n // Use bitmask to track used digits\n memo = new int[num.length()][1 << 10][2];\n for (int[][] arr : memo) {\n for (int[] row : arr) Arrays.fill(row, -1);\n }\n\n return solve(0, 0, 1, false);\n }\n\n private int solve(int pos, int usedMask, int tight, boolean started) {\n if (pos == num.length()) {\n return started ? 1 : 0; // Don't count 0\n }\n\n int key = (tight << 10) | usedMask;\n if (!started && memo[pos][usedMask][tight] != -1) {\n return memo[pos][usedMask][tight];\n }\n\n int limit = tight == 1 ? (num.charAt(pos) - '0') : 9;\n int result = 0;\n\n // Option: continue with leading zeros\n if (!started) {\n result += solve(pos + 1, usedMask, 0, false);\n }\n\n int start = started ? 0 : 1; // Can't start with 0\n for (int digit = start; digit <= limit; digit++) {\n if ((usedMask & (1 << digit)) != 0) continue; // Already used\n\n int newMask = usedMask | (1 << digit);\n int newTight = (tight == 1 && digit == limit) ? 1 : 0;\n result += solve(pos + 1, newMask, newTight, true);\n }\n\n if (!started) {\n memo[pos][usedMask][tight] = result;\n }\n return result;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: DP Optimizations\n\n### Convex Hull Trick\n\nFor recurrences of form: `dp[i] = min(dp[j] + a[i] * b[j])` where b is monotonic.\n\n```java\npublic class ConvexHullTrick {\n // Lines of form y = mx + c, stored in ArrayList for indexed access\n private List hull = new ArrayList<>();\n private int head = 0; // Pointer for query optimization\n\n // Add line y = mx + c (m must be decreasing)\n public void addLine(long m, long c) {\n long[] line = {m, c};\n while (hull.size() - head >= 2 && bad(hull.get(hull.size() - 2), line)) {\n hull.remove(hull.size() - 1);\n }\n hull.add(line);\n }\n\n // Query minimum y for given x (x must be increasing)\n public long query(long x) {\n while (hull.size() - head >= 2 &&\n eval(hull.get(head), x) >= eval(hull.get(head + 1), x)) {\n head++;\n }\n return eval(hull.get(head), x);\n }\n\n private long eval(long[] line, long x) {\n return line[0] * x + line[1];\n }\n\n private boolean bad(long[] l0, long[] l2) {\n // Check if last line in hull is useless (never optimal)\n long[] l1 = hull.get(hull.size() - 1);\n return (l1[1] - l0[1]) * (l2[0] - l1[0]) >=\n (l2[1] - l1[1]) * (l1[0] - l0[0]);\n }\n}\n\n// Example: dp[i] = min(dp[j] + a[i] * b[j]) for j < i\npublic class ConvexHullDP {\n public long solve(long[] a, long[] b) {\n int n = a.length;\n long[] dp = new long[n];\n ConvexHullTrick cht = new ConvexHullTrick();\n\n dp[0] = 0; // Base case\n cht.addLine(b[0], dp[0]);\n\n for (int i = 1; i < n; i++) {\n dp[i] = cht.query(a[i]);\n cht.addLine(b[i], dp[i]);\n }\n\n return dp[n - 1];\n }\n}\n```\n\n### Divide and Conquer Optimization\n\nFor recurrences where optimal split point is monotonic.\n\n```java\npublic class DivideAndConquerOptimization {\n private int[][] cost; // cost[i][j] = cost of segment [i, j]\n private int[][] dp;\n private int n, k;\n\n // dp[i][j] = min cost to partition first j elements into i groups\n // Condition: opt[i][j] <= opt[i][j+1]\n\n public int solve(int[][] cost, int n, int k) {\n this.cost = cost;\n this.n = n;\n this.k = k;\n dp = new int[k + 1][n + 1];\n\n for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);\n dp[0][0] = 0;\n\n for (int i = 1; i <= k; i++) {\n compute(i, 1, n, 0, n - 1);\n }\n\n return dp[k][n];\n }\n\n private void compute(int i, int jLo, int jHi, int optLo, int optHi) {\n if (jLo > jHi) return;\n\n int jMid = (jLo + jHi) / 2;\n int opt = optLo;\n\n for (int m = optLo; m <= Math.min(optHi, jMid - 1); m++) {\n if (dp[i - 1][m] != Integer.MAX_VALUE) {\n int val = dp[i - 1][m] + cost[m][jMid - 1];\n if (val < dp[i][jMid]) {\n dp[i][jMid] = val;\n opt = m;\n }\n }\n }\n\n compute(i, jLo, jMid - 1, optLo, opt);\n compute(i, jMid + 1, jHi, opt, optHi);\n }\n}\n```\n\n### Space Optimization Techniques\n\n```java\npublic class SpaceOptimization {\n // 2D to 1D when only previous row needed\n public int optimized2Dto1D(int n, int m) {\n // Original: dp[i][j] depends on dp[i-1][...]\n int[] prev = new int[m];\n int[] curr = new int[m];\n\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n curr[j] = /*compute from prev*/;\n }\n int[] temp = prev; prev = curr; curr = temp;\n }\n return prev[m - 1];\n }\n\n // Single row with careful ordering (0/1 Knapsack)\n public int singleRow(int[] weights, int[] values, int capacity) {\n int[] dp = new int[capacity + 1];\n for (int i = 0; i < weights.length; i++) {\n // 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 return dp[capacity];\n }\n\n // Bitmask compression for subset DP\n public int bitmaskCompression(int n) {\n // Only keep masks with specific popcount\n // Use map instead of full 2^n array\n Map dp = new HashMap<>();\n // ...\n return 0;\n }\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Bitmask Overflow\n\n```java\n// ❌ WRONG: 1 is int, overflow for n > 30\nint mask = 1 << n; // Overflow if n >= 31\n\n// ✅ CORRECT: Use long for larger n\nlong mask = 1L << n; // Works for n up to 62\n```\n\n---\n\n### Mistake 2: Tree DP Parent Check\n\n```java\n// ❌ WRONG: Visiting parent as child\nfor (int child : adj.get(node)) {\n dfs(child, node); // Will revisit parent!\n}\n\n// ✅ CORRECT: Skip parent\nfor (int child : adj.get(node)) {\n if (child != parent) {\n dfs(child, node);\n }\n}\n```\n\n---\n\n### Mistake 3: Digit DP Leading Zeros\n\n```java\n// ❌ WRONG: Not handling leading zeros properly\n// Counting \"007\" as valid when we want 7\n\n// ✅ CORRECT: Track whether number has started\nprivate int solve(int pos, int state, int tight, boolean started) {\n if (!started && digit == 0) {\n // Still in leading zeros\n return solve(pos + 1, state, 0, false);\n }\n // ...\n}\n```\n\n---\n\n## 🐛 Debug This: Bitmask DP Bug\n\nThis TSP implementation has a bug. Can you find it?\n\n```java\npublic int tsp(int[][] dist) {\n int n = dist.length;\n int[][] dp = new int[1 << n][n];\n for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);\n\n dp[1][0] = 0;\n\n for (int mask = 1; mask < (1 << n); mask++) {\n for (int last = 0; last < n; last++) {\n // BUG IS SOMEWHERE HERE\n if (dp[mask][last] == Integer.MAX_VALUE) continue;\n\n for (int next = 0; next < n; next++) {\n if ((mask & (1 << next)) != 0) continue;\n\n int newMask = mask | (1 << next);\n dp[newMask][next] = Math.min(\n dp[newMask][next],\n dp[mask][last] + dist[last][next]\n );\n }\n }\n }\n\n int fullMask = (1 << n) - 1;\n return dp[fullMask][0]; // BUG!\n}\n```\n\n

🔍 Click to reveal the bug

\n\n**Bug**: The return statement assumes we end at city 0, but we need to return TO city 0.\n\n```java\n// ❌ BUG: Returns dp[fullMask][0] - minimum to END at 0\nreturn dp[fullMask][0];\n\n// ✅ FIX: Find minimum cost ending at any city + return to 0\nint ans = Integer.MAX_VALUE;\nfor (int last = 1; last < n; last++) {\n if (dp[fullMask][last] != Integer.MAX_VALUE) {\n ans = Math.min(ans, dp[fullMask][last] + dist[last][0]);\n }\n}\nreturn ans;\n```\n\nAlso missing: check that `(mask & (1 << last)) != 0` before processing.\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Binary Tree Cameras ⭐⭐⭐\n\nPlace minimum cameras on tree nodes such that every node is monitored.\n\n```java\npublic int minCameraCover(TreeNode root) {\n // States: 0=not covered, 1=covered no camera, 2=has camera\n}\n```\n\n---\n\n### Exercise 2: Shortest Superstring ⭐⭐⭐⭐\n\nFind shortest string containing all given strings as substrings.\n\n```java\npublic String shortestSuperstring(String[] words) {\n // Bitmask DP: dp[mask][last] = min length ending with words[last]\n}\n```\n\n---\n\n### Exercise 3: Count Numbers with Even Digit Sum ⭐⭐⭐\n\nCount numbers in [1, n] where digit sum is even.\n\n```java\npublic long countEvenDigitSum(long n) {\n // Digit DP with parity tracking\n}\n```\n\n---\n\n### Exercise 4: Parallel Courses III ⭐⭐⭐⭐\n\nFind minimum time to complete all courses with dependencies (Tree DP with multiple children).\n\n```java\npublic int minimumTime(int n, int[][] relations, int[] time) {\n // dp[i] = minimum time to complete course i and all prerequisites\n}\n```\n\n---\n\n### Exercise 5: Minimum Cost to Merge Stones ⭐⭐⭐⭐\n\nMerge k consecutive piles into one, minimize cost.\n\n```java\npublic int mergeStones(int[] stones, int k) {\n // Interval DP: dp[i][j] = min cost to merge [i,j] into fewest piles\n}\n```\n\n---\n\n## 🎤 Interview Questions\n\n### Q1: \"When would you choose bitmask DP over other approaches?\"\n\n**Answer**:\n\nUse bitmask DP when:\n1. **Small n** (typically n ≤ 20-25)\n2. **Subset-based state**: Need to track which elements are \"selected\"\n3. **Permutation/combination problems**: Assignment, TSP\n4. **Exponential nature**: Problem inherently requires checking subsets\n\n**Comparison**:\n- Bitmask: O(2^n × n) - good for small n\n- Backtracking: Can prune but worst case O(n!)\n- Greedy: O(n log n) but may not be optimal\n\n---\n\n### Q2: \"How do you identify if a problem can use convex hull trick?\"\n\n**Answer**:\n\nLook for recurrence of form:\n```\ndp[i] = min/max over j of: dp[j] + f(i) × g(j) + h(i) + k(j)\n```\n\nWhere:\n- f(i) × g(j) is the \"multiplicative\" term\n- f(i) is the query value\n- g(j) is the line slope\n- dp[j] + k(j) is the line intercept\n\n**Requirements**:\n1. Either g(j) is monotonic (slopes sorted)\n2. Or f(i) is monotonic (queries sorted)\n3. Or use Li Chao tree for arbitrary queries\n\n---\n\n### Q3: \"Explain the difference between memoization in tree DP vs standard DP.\"\n\n**Answer**:\n\n**Standard DP**:\n- Clear topological order (array indices)\n- Subproblems indexed by simple states\n- Can iterate or recurse\n\n**Tree DP**:\n- Order determined by tree structure (post-order)\n- Subproblems are subtrees\n- Usually recursive DFS\n- Parent pointer needed to avoid revisiting\n\n```java\n// Standard: clear iteration order\nfor (int i = 1; i <= n; i++) {\n dp[i] = compute(dp[i-1], ...);\n}\n\n// Tree: must traverse structure\nvoid dfs(int node, int parent) {\n for (int child : adj[node]) {\n if (child != parent) {\n dfs(child, node);\n // Combine child's dp into node's\n }\n }\n}\n```\n\n---\n\n### Q4: \"How would you solve TSP for n=30 cities?\"\n\n**Answer**:\n\nFor n=30, O(n² × 2^n) is too slow. Options:\n\n1. **Branch and bound** with good pruning\n2. **Approximation algorithms**:\n - Christofides: 1.5× optimal for metric TSP\n - 2-opt local search\n\n3. **Held-Karp relaxation** (exponential but practical)\n\n4. **Divide and conquer**:\n - Split cities geographically\n - Solve sub-TSPs\n - Merge solutions\n\n5. **Randomized/genetic algorithms** for near-optimal\n\nFor exact solution with n=30, specialized solvers like Concorde are needed.\n\n---\n\n### Q5: \"How does digit DP handle the 'tight' constraint?\"\n\n**Answer**:\n\n```\nNumber: 234\nPosition 0: tight=1 → can only use 0,1,2\n If we choose 2, next position still tight\n If we choose 0 or 1, next positions not tight\n\nPosition 1 (after choosing 2): tight=1 → can only use 0,1,2,3\n If we choose 3, next position still tight\n ...\n\nTight means: \"we've matched the prefix of N exactly\"\nNot tight means: \"we're already less than N, so remaining digits can be anything\"\n```\n\n```java\nint newTight;\nif (tight && digit == limit) {\n newTight = 1; // Still matching N's prefix\n} else {\n newTight = 0; // Already less than N\n}\n```\n\n---\n\n## 📋 Quick Reference\n\n### Complexity Summary\n\n| Technique | Time | Space | When to Use |\n|-----------|------|-------|-------------|\n| Tree DP | O(n) | O(n) | Tree structure |\n| Bitmask DP | O(2^n × n) | O(2^n) | n ≤ 20 |\n| Digit DP | O(D × S × 2) | O(D × S) | Count in range |\n| CHT | O(n) | O(n) | Linear DP optimization |\n| D&C Opt | O(kn log n) | O(kn) | Monotonic opt point |\n\n### State Templates\n\n```java\n// Tree DP\nint[][] dp = new int[n][states]; // dp[node][state]\n\n// Bitmask DP\nint[][] dp = new int[1 << n][n]; // dp[mask][last]\n\n// Digit DP\nint[][][][] dp = new int[digits][sum][2][2]; // [pos][state][tight][started]\n```\n\n### Bit Manipulation Cheatsheet\n\n```java\n// Set operations\nmask | (1 << i) // Add element i\nmask & ~(1 << i) // Remove element i\nmask & (1 << i) // Check if i in set\nmask ^ (1 << i) // Toggle element i\nInteger.bitCount(mask) // Count elements\nmask & (mask - 1) // Remove lowest bit\nmask & (-mask) // Get lowest bit\n```\n\n---\n\n## 🔗 What's Next?\n\nIn **Part 19: Greedy Algorithms**, we'll explore:\n- Greedy choice property\n- Activity selection\n- Huffman coding\n- Fractional knapsack\n- Job scheduling\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| 0 | Full read + Tree DP exercise | 90 min |\n| 1 | Quick Reference | 10 min |\n| 3 | Implement TSP from memory | 25 min |\n| 7 | Digit DP exercise | 30 min |\n| 14 | Debug exercise + optimization | 20 min |\n| 30 | Interview questions | 15 min |\n\n---\n\n**Next**: [Part 19: Greedy Algorithms →](./algorithms-part-19-greedy-algorithms.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.283827Z","createdAt","2026-06-10T07:19:25.284512Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",20,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",18,"author",{"_31":55,"_99":57,"_100":101,"_102":103,"_104":-5,"_105":-5,"_106":-5,"_107":-5,"_108":-5},"category",{"_31":95,"_73":59,"_35":96,"_76":97,"_98":-5},"tags",[79,80,81,82],"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":92,"_73":93,"_35":94},{"_31":89,"_73":90,"_35":91},{"_31":86,"_73":87,"_35":88},{"_31":83,"_73":84,"_35":85},192,"Tree Dp","tree-dp",194,"Digit Dp","digit-dp",195,"Convex Hull Trick","convex-hull-trick",193,"Bitmask Dp","bitmask-dp",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]