5.1 Advanced DP — DSA Crash Course

Deep Dive: Beyond 1D and 2D Tables

Beginner tip: Advanced DP is for when simple dp[i] or dp[i][j] is not enough. Bitmask DP uses binary numbers to represent which items are selected (works when n is less than or equal to 20). DP on trees processes children before parents. Interval DP solves ranges like "best way to split string from i to j." These are Hard-level topics -- skip them if you are short on time.

Bitmask DP -- Assign N Tasks to N People

3 people, 3 tasks. Cost matrix:

        Task 0  Task 1  Task 2
Person 0:  9      2       7
Person 1:  6      4       3
Person 2:  5      8       1

mask=0b000 (no tasks assigned), assign person 0 first:
  Assign task 0: cost=9, next state=0b001
  Assign task 1: cost=2, next state=0b010
  Assign task 2: cost=7, next state=0b100

For mask=0b001 (task 0 taken), assign person 1:
  Assign task 1: cost=4, next=0b011
  Assign task 2: cost=3, next=0b101

DP: dp[mask] = min cost to assign tasks in mask.
Total states: 2^3 = 8. For n=20: 2^20 = 1M (feasible).

Interval DP -- Burst Balloons

nums = [3, 1, 5, 8] (padded with 1s: [1, 3, 1, 5, 8, 1])

dp[i][j] = max coins from bursting all balloons in range (i..j)

For range (1..4), try each as the LAST balloon to burst:
  Last=1 (val 3): dp[1][0] + 1*3*1 + dp[2][4] (? invalid)
  
  Build bottom-up from small ranges:
  dp[1][1] = 1*3*1 = 3   (only balloon 3, neighbors are padding 1s)
  dp[2][2] = 3*1*5 = 15
  dp[3][3] = 1*5*8 = 40
  dp[4][4] = 5*8*1 = 40
  ... build up to dp[1][4]

Key: "last to burst" thinking avoids dependency issues. When k is the last balloon in (i..j), its neighbors are nums[i-1] and nums[j+1] (everything else already popped).

Before You Start -- How to Think About Advanced DP

When Basic DP Isn't Enough

Basic DP uses dp[i] or dp[i][j]. Advanced DP encodes more complex state:

Technique	State Encoding	When to Use
Bitmask DP	`dp[mask]` where mask = set of items used	n <= 20, "assign tasks", "visit all cities"
DP on Trees	`dp[node]` = answer for subtree	Tree problems with choices at each node
Digit DP	`dp[pos][tight][...]`	"Count numbers with property X up to N"
DP + BS	DP with binary search to find transition	LIS in O(n log n)
Interval DP	`dp[i][j]` = answer for range [i..j]	"Burst balloons", matrix chain

Bitmask DP

Key insight: When n <= 20, you can represent a SUBSET as a bitmask (integer).
  mask = 0b10110 means items {1, 2, 4} are selected.
  Check if item i is in mask: mask & (1 << i)
  Add item i to mask: mask | (1 << i)
  Total states: 2^n (fits in memory for n <= 20)

DP on Trees

Process children FIRST (post-order), then compute answer for parent.
  dp[node] typically depends on dp[left] and dp[right] (or all children).
  Example: House Robber III:
    dp[node] = max(rob this node + skip children, skip this node + rob children)

Interval DP

Solve for small ranges first, build up to larger ranges.
  for length in range(2, n+1):
    for i in range(n - length + 1):
      j = i + length - 1
      dp[i][j] = best over all split points k in [i..j]

These are Hard-level topics. If time is limited, prioritize Bitmask DP and DP on Trees.

Topics

#	Topic	Status
1	Bitmask DP (TSP, Assign Jobs)	[ ]
2	DP on Trees (House Robber III)	[ ]
3	Digit DP	[ ]
4	DP + Binary Search (LIS in O(n log n))	[ ]
5	DP on Intervals (Burst Balloons)	[ ]
6	State Compression (2D -> 1D)	[ ]

Worked Code Examples

Each technique with the smallest runnable Python that captures its essence. Read the snippet, then trace it on paper for n = 3 or 4.

1. Bitmask DP — Assign N Tasks to N People (minimum cost)

def assign_tasks(cost):  # cost[person][task]
    n = len(cost)
    INF = float('inf')
    # dp[mask] = min cost to assign the tasks indicated by `mask` to the
    # first popcount(mask) people. The next person to assign is popcount(mask).
    dp = [INF] * (1 << n)
    dp[0] = 0
    for mask in range(1 << n):
        if dp[mask] == INF:
            continue
        person = bin(mask).count("1")          # next person to assign
        if person == n:
            continue
        for task in range(n):
            if mask & (1 << task):              # task already taken
                continue
            new_mask = mask | (1 << task)
            dp[new_mask] = min(dp[new_mask], dp[mask] + cost[person][task])
    return dp[(1 << n) - 1]

# Time:  O(n^2 * 2^n)  — 2^n states, n transitions each, n work per transition.
# Space: O(2^n).
# Feasible up to n ≈ 20 (2^20 = ~1M states).

2. DP on Trees — House Robber III (LeetCode 337)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

class Solution:
    def rob(self, root):
        # Returns (rob_this, skip_this) for the subtree rooted at node.
        def helper(node):
            if not node:
                return (0, 0)
            l_rob, l_skip = helper(node.left)
            r_rob, r_skip = helper(node.right)
            rob_this  = node.val + l_skip + r_skip          # rob node → must skip children
            skip_this = max(l_rob, l_skip) + max(r_rob, r_skip)  # take the better of each child
            return (rob_this, skip_this)
        return max(helper(root))

# Time:  O(n) — every node visited once.
# Space: O(h) — recursion stack proportional to tree height.
# The trick: returning a TUPLE per node lets the parent pick the better
# combination without re-traversing children.

3. LIS in O(n log n) — Patience Sorting

The naive O(n²) LIS is dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]). The O(n log n) version uses patience sorting: imagine dealing cards left to right and placing each on the leftmost pile whose top card is ≥ this card (or starting a new pile if none qualifies). The number of piles at the end equals the LIS length.

from bisect import bisect_left

def length_of_lis(nums):
    tails = []  # tails[k] = smallest tail of any increasing subseq of length k+1
    for x in nums:
        i = bisect_left(tails, x)   # leftmost pile whose top >= x
        if i == len(tails):
            tails.append(x)         # start a new pile
        else:
            tails[i] = x            # replace top of that pile (smaller tail = more room to grow)
    return len(tails)

# Time:  O(n log n) — bisect_left is O(log n) per element.
# Space: O(n).
# `tails` is NOT the LIS itself — it's a sorted invariant that tracks the
# minimum-tail trick. Reconstructing the actual LIS needs a parent-pointer
# array; rare in interviews.

4. Interval DP — Matrix Chain Multiplication (the canonical pattern)

def matrix_chain(dims):
    # dims[i] x dims[i+1] is the i-th matrix.
    # dp[i][j] = min scalar multiplications to compute matrices i..j.
    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):                  # solve smaller intervals first
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):                   # try every split point
                cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                if cost < dp[i][j]:
                    dp[i][j] = cost
    return dp[0][n - 1]

# Time:  O(n^3) — n^2 intervals, n split points each.
# Space: O(n^2).
# Same shape as Burst Balloons, Optimal BST, Palindrome Partitioning II — every
# interval-DP problem fills the table by interval length and tries every split.

In an interview, present these in the order simplest framing → optimisation: bitmask if n ≤ 20, tree-DP for tree problems, interval-DP for "split a sequence/range optimally", and patience-sort LIS only if asked to optimise the obvious O(n²).