Skip to main content

Advanced DP and Optimization Clinic

Retrieval Prompts​

  1. Write the interval-DP recurrence dp[i][j] = min over k of ( dp[i][k] + dp[k+1][j] + cost(i, k, j) ) and explain the fill order.
  2. Write the matrix-chain recurrence in terms of p[0..n].
  3. Describe the tree-DP recurrence for maximum independent set with the two states dp[v][0] and dp[v][1].
  4. Write the bitmask-TSP state and recurrence for dp[S][j].
  5. State the exchange-argument template in two sentences.

Compare and Distinguish​

Separate these pairs clearly:

  • interval DP versus sequence DP (range as state vs prefix as state)
  • tree DP versus linear DP (post-order DFS vs left-to-right fill)
  • bitmask DP versus regular DP (2^n * n state space vs n^k)
  • greedy-with-proof versus heuristic (provable optimum vs "it usually works")
  • DP on a DAG versus DP on a general graph (polynomial longest path vs NP-hard)

Common Mistake Check​

For each statement, identify the error:

  1. "Matrix chain DP can be filled in row-major order because dp[i][j] only reads dp[i'][j'] for i' <= i and j' <= j."
  2. "For balloon burst, recursing on the first balloon burst in the range is natural and clean."
  3. "In tree DP, always pick the root at vertex 0; anything else complicates the recurrence."
  4. "For TSP with n = 25, bitmask DP is fast enough."
  5. "Greedy works for 0/1 knapsack because the greedy 'largest value-per-weight ratio first' is a provable exchange argument."
  6. "Longest path in any graph can be computed by topological DP."

Mini Application​

For each task, state the paradigm (greedy, DP-sequence, DP-interval, DP-tree, DP-bitmask, DP-on-DAG, or graph-algorithm), justify in one sentence, then write recurrence and complexity.

  1. Given a chain of matrices with dimensions p[0..n], find the minimum cost and the optimal parenthesization.
  2. Given n balloons with values a[1..n], maximize total points from bursting (standard balloon-burst problem).
  3. Given a tree of n nodes with weights, compute the maximum-weight independent set.
  4. Given an n ≤ 16 complete graph with edge costs, compute the minimum-cost Hamiltonian tour.
  5. Given a DAG with edge weights, compute the longest path from any source to any sink (critical path).
  6. Given activities with start/finish times, maximize the count of mutually non-overlapping activities.
  7. Given an arbitrary graph with nonnegative edges, compute shortest path from s to t. (Not DP -- name the correct algorithm.)
  8. Given an array of n integers, decide whether a subset sums to T, for T ≤ 10^5.

Evidence Check​

This page is complete only if, for each of the eight problems, you have named the correct paradigm before writing any code, written a short justification, and implemented at least three of them with passing tests on small inputs.