Notes

Dynamic programming is applicable when a problem has two properties: overlapping subproblems (the same subproblem is solved multiple times in a naive recursive approach) and optimal substructure (an optimal solution can be constructed from optimal solutions to subproblems).

The core patterns to recognize:

1. 1D DP — State is a single index. Classic examples: Fibonacci, climbing stairs, house robber. Ask: what's the recurrence relating dp[i] to dp[i-1] or dp[i-2]?

2. 2D DP — State is two indices, often (i, j) representing positions in two sequences. Classic: longest common subsequence, edit distance. The table fills left-to-right, top-to-bottom.

3. Interval DP — State is a range [i, j]. Classic: matrix chain multiplication, burst balloons. Usually requires iterating over interval length first.

4. Knapsack variants — Choosing items with constraints. 0/1 knapsack, unbounded knapsack, subset sum. Key: does order matter? Can items repeat?

The mental model shift that makes DP click: stop thinking recursively top-down and start thinking about which previous states you need to answer the current state. Define the state, write the recurrence, handle the base cases, decide the order of iteration.

Expected prediction error can be decomposed into three components: bias squared, variance, and irreducible noise. The last term is a floor you can't beat — it's inherent randomness in the data. The first two are what model selection actually controls.

Bias is error from wrong assumptions in the learning algorithm. High bias means the model is too simple — it underfits. A linear model on a cubic relationship has high bias regardless of how much data you throw at it.

Variance is error from sensitivity to fluctuations in training data. High variance means the model is too complex — it memorizes training noise and fails to generalize. A deep decision tree with no pruning is a classic high-variance model.

The tradeoff: reducing bias (more complex model) tends to increase variance, and vice versa. The goal is to find the sweet spot.

In practice: if train error is high, you have a bias problem — make the model more expressive. If train error is low but validation error is high, you have a variance problem — regularize, get more data, or simplify. This diagnostic framework is more useful than the math in most real situations.