• When and Why DP
• States, Transitions, and Base Cases
• Top-Down (Memo) vs Bottom-Up (Tabulation)
• 0/1 and Unbounded Knapsack
• LIS: O(n^2) DP and O(n log n) Patience
• Tree DP
• Techniques: Space Opt, Bitset, Convex Hull Trick
• Exercises

Use DP when subproblems overlap and exhibit optimal substructure. Replace exponential recursion with polynomial-time tabulation or memoization.

• Identify: brute-force recursion with repeated work, greedy fails, obvious subproblem decomposition.
• Goal: define minimal state capturing all necessary history.
• Complexity: states × transitions per state.

Checklist:
1) State definition: dp[i][...]= meaning
2) Base cases: dp[0][...], empty, impossible = -∞/∞
3) Transition: how to go from smaller to larger states
4) Order: topological order consistent with dependencies
5) Answer: which state(s) encode the final solution

• Top-Down (memoization): natural recursion, compute only needed states.
• Bottom-Up (tabulation): iterative, has clearer complexity and easier space optimizations.
• Order: DAG ordering of dependencies; for 1D/2D, use loops with correct direction.

// 0/1 knapsack: maximize value with weight limit W
function knapsack01(weights, values, W) {
  const dp = Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = W; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[W];
}

// Unbounded knapsack (unlimited items)
function knapsackUnbounded(weights, values, W) {
  const dp = Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = weights[i]; w <= W; w++) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[W];
}

// O(n log n) LIS length via patience sorting
function LISLength(a) {
  const tails = [];
  for (const x of a) {
    let l = 0, r = tails.length;
    while (l < r) {
      const m = (l + r) >> 1;
      if (tails[m] < x) l = m + 1; else r = m;
    }
    tails[l] = x;
  }
  return tails.length;
}

// Maximum independent set on a tree
function treeMIS(n, adj) {
  const dp0 = Array(n).fill(0); // exclude node
  const dp1 = Array(n).fill(0); // include node
  function dfs(u, p) {
    dp1[u] = 1;
    for (const v of adj[u]) if (v !== p) {
      dfs(v, u);
      dp0[u] += Math.max(dp0[v], dp1[v]);
      dp1[u] += dp0[v];
    }
  }
  dfs(0, -1);
  return Math.max(dp0[0], dp1[0]);
}

• Space optimization: roll arrays when transition uses only previous row/col.
• Bitset DPs: speed up subset sums and knapsack with word-level ops.
• Convex Hull Trick: optimize DP of form dp[i] = min_j (m_j x_i + b_j).
• Divide & Conquer / Knuth optimization: reduce transitions under quadrangle inequality or monotonicity.

1. Implement 0/1 knapsack with item reconstruction.
2. Compute LIS and return one optimal sequence.
3. Tree DP: count the number of independent sets modulo 1e9+7.