Advanced DP Techniques

📋 At a Glance

┌─────────────────────────────────────────────────────────────────┐
│                  ADVANCED DP TECHNIQUES                         │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  TREE DP                        BITMASK DP                      │
│  ┌─────────────────┐            ┌─────────────────┐             │
│  │       1         │            │ Subset: 1011    │             │
│  │      /|\        │            │ = {0, 1, 3}     │             │
│  │     2 3 4       │            │                 │             │
│  │    /|           │            │ TSP: visit all  │             │
│  │   5 6           │            │ cities exactly  │             │
│  │                 │            │ once            │             │
│  │ dp[node] from   │            │                 │             │
│  │ children        │            │ dp[mask][last]  │             │
│  └─────────────────┘            └─────────────────┘             │
│                                                                 │
│  DIGIT DP                       OPTIMIZATIONS                   │
│  ┌─────────────────┐            ┌─────────────────┐             │
│  │ Count numbers   │            │ • Convex Hull   │             │
│  │ with property   │            │   Trick         │             │
│  │ in range [L,R]  │            │                 │             │
│  │                 │            │ • Divide &      │             │
│  │ dp[pos][state]  │            │   Conquer Opt   │             │
│  │ [tight][started]│            │                 │             │
│  │                 │            │ • Knuth's Opt   │             │
│  └─────────────────┘            └─────────────────┘             │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🎯 What You'll Learn

After completing this article, you will be able to:

1. Solve tree problems: Apply DP on tree structures
2. Use bitmask DP: Solve problems with small state spaces
3. Apply digit DP: Count numbers with specific properties
4. Optimize transitions: Use convex hull trick and other optimizations
5. Reduce space complexity: Rolling arrays and state compression

🔥 Production Story: The Delivery Route Optimizer

A delivery company needed to optimize routes for drivers visiting multiple locations daily.

The Problem

JAVA(17 lines)
Code
Loading syntax highlighter...

The Solution: Bitmask DP

JAVA(39 lines)
Code
Loading syntax highlighter...

The Impact

🔬 Deep Dive: DP on Trees

The Concept

Tree DP computes solutions bottom-up from leaves to root.

┌─────────────────────────────────────────────────────────────────┐
│                    TREE DP PATTERN                              │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│          1 (root)                                               │
│         /|\                                                     │
│        2 3 4          Process order: 5,6,2,3,4,1                │
│       /|              (post-order: children before parent)      │
│      5 6                                                        │
│                                                                 │
│  Pattern:                                                       │
│  void dfs(int node, int parent) {                               │
│      for (int child : adj[node]) {                              │
│          if (child != parent) {                                 │
│              dfs(child, node);                                  │
│              // Combine child's DP into node's DP               │
│          }                                                      │
│      }                                                          │
│      // Compute dp[node] from dp[children]                      │
│  }                                                              │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Example: Maximum Independent Set in Tree

JAVA(37 lines)
Code
Loading syntax highlighter...

Tree Diameter

JAVA(38 lines)
Code
Loading syntax highlighter...

Tree DP with Rerooting

For problems where we need the answer for each node as root:

JAVA(68 lines)
Code
Loading syntax highlighter...
Show all 68 lines

🔬 Deep Dive: Bitmask DP

When to Use

• Small number of elements (n ≤ 20-25)
• Need to track which elements are "selected"
• Subset-based state transitions

Bit Manipulation Essentials

JAVA(39 lines)
Code
Loading syntax highlighter...

TSP (Traveling Salesman Problem)

JAVA(37 lines)
Code
Loading syntax highlighter...

Assignment Problem (Matching)

JAVA(25 lines)
Code
Loading syntax highlighter...

Subset Sum with Exact Selection

JAVA(48 lines)
Code
Loading syntax highlighter...
Show all 48 lines

🔬 Deep Dive: Digit DP

The Concept

Count numbers in range [L, R] with certain properties by processing digit by digit.

┌─────────────────────────────────────────────────────────────────┐
│                    DIGIT DP PATTERN                             │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Count numbers from 0 to N with property P                      │
│                                                                 │
│  Example: N = 234, count numbers with digit sum ≤ 10            │
│                                                                 │
│  State: dp[pos][sum][tight][started]                            │
│  - pos: current digit position                                  │
│  - sum: running digit sum                                       │
│  - tight: are we still bounded by N?                            │
│  - started: have we placed a non-zero digit?                    │
│                                                                 │
│  For N = 234:                                                   │
│  - If tight and pos=0, digit can be 0,1,2 (not 3+)              │
│  - If not tight, digit can be 0-9                               │
│                                                                 │
│  To count [L, R]: count(R) - count(L-1)                         │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Count Numbers with Digit Sum ≤ K

JAVA(47 lines)
Code
Loading syntax highlighter...
Show all 47 lines

Count Numbers Without Digit 4

JAVA(30 lines)
Code
Loading syntax highlighter...

Count Numbers with No Repeated Digits

JAVA(48 lines)
Code
Loading syntax highlighter...
Show all 48 lines

🔬 Deep Dive: DP Optimizations

Convex Hull Trick

JAVA(53 lines)
Code
Loading syntax highlighter...
Show all 53 lines

Divide and Conquer Optimization

For recurrences where optimal split point is monotonic.

JAVA(44 lines)
Code
Loading syntax highlighter...
Show all 44 lines

Space Optimization Techniques

JAVA(37 lines)
Code
Loading syntax highlighter...

⚠️ Common Mistakes

Mistake 1: Bitmask Overflow

JAVA(5 lines)
Code
Loading syntax highlighter...

Mistake 2: Tree DP Parent Check

JAVA(11 lines)
Code
Loading syntax highlighter...

Mistake 3: Digit DP Leading Zeros

JAVA(11 lines)
Code
Loading syntax highlighter...

🐛 Debug This: Bitmask DP Bug

This TSP implementation has a bug. Can you find it?

JAVA(27 lines)
Code
Loading syntax highlighter...

JAVA(11 lines)
Code
Loading syntax highlighter...

💻 Exercises

Exercise 1: Binary Tree Cameras ⭐⭐⭐

Place minimum cameras on tree nodes such that every node is monitored.

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 2: Shortest Superstring ⭐⭐⭐⭐

Find shortest string containing all given strings as substrings.

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 3: Count Numbers with Even Digit Sum ⭐⭐⭐

Count numbers in [1, n] where digit sum is even.

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 4: Parallel Courses III ⭐⭐⭐⭐

Find minimum time to complete all courses with dependencies (Tree DP with multiple children).

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 5: Minimum Cost to Merge Stones ⭐⭐⭐⭐

Merge k consecutive piles into one, minimize cost.

JAVA(3 lines)
Code
Loading syntax highlighter...

🎤 Interview Questions

Q1: "When would you choose bitmask DP over other approaches?"

Use bitmask DP when:

1. Small n (typically n ≤ 20-25)
2. Subset-based state: Need to track which elements are "selected"
3. Permutation/combination problems: Assignment, TSP
4. Exponential nature: Problem inherently requires checking subsets

• Bitmask: O(2^n × n) - good for small n
• Backtracking: Can prune but worst case O(n!)
• Greedy: O(n log n) but may not be optimal

Q2: "How do you identify if a problem can use convex hull trick?"

Look for recurrence of form:

dp[i] = min/max over j of: dp[j] + f(i) × g(j) + h(i) + k(j)

Where:

• f(i) × g(j) is the "multiplicative" term
• f(i) is the query value
• g(j) is the line slope
• dp[j] + k(j) is the line intercept

1. Either g(j) is monotonic (slopes sorted)
2. Or f(i) is monotonic (queries sorted)
3. Or use Li Chao tree for arbitrary queries

Q3: "Explain the difference between memoization in tree DP vs standard DP."

• Clear topological order (array indices)
• Subproblems indexed by simple states
• Can iterate or recurse

• Order determined by tree structure (post-order)
• Subproblems are subtrees
• Usually recursive DFS
• Parent pointer needed to avoid revisiting

JAVA(14 lines)
Code
Loading syntax highlighter...

Q4: "How would you solve TSP for n=30 cities?"

For n=30, O(n² × 2^n) is too slow. Options:

1. Branch and bound with good pruning
2. Approximation algorithms:
   • Christofides: 1.5× optimal for metric TSP
   • 2-opt local search
3. Held-Karp relaxation (exponential but practical)
4. Divide and conquer:
   • Split cities geographically
   • Solve sub-TSPs
   • Merge solutions
5. Randomized/genetic algorithms for near-optimal

For exact solution with n=30, specialized solvers like Concorde are needed.

Q5: "How does digit DP handle the 'tight' constraint?"

Number: 234
Position 0: tight=1 → can only use 0,1,2
         If we choose 2, next position still tight
         If we choose 0 or 1, next positions not tight

Position 1 (after choosing 2): tight=1 → can only use 0,1,2,3
         If we choose 3, next position still tight
         ...

Tight means: "we've matched the prefix of N exactly"
Not tight means: "we're already less than N, so remaining digits can be anything"

JAVA(6 lines)
Code
Loading syntax highlighter...

📋 Quick Reference

Complexity Summary

State Templates

JAVA(8 lines)
Code
Loading syntax highlighter...

Bit Manipulation Cheatsheet

JAVA(8 lines)
Code
Loading syntax highlighter...

🔗 What's Next?

• Greedy choice property
• Activity selection
• Huffman coding
• Fractional knapsack
• Job scheduling

📅 Review Schedule