Dynamic Programming

Overlapping subproblems means the same subproblem instance, with identical arguments, is solved repeatedly. Naive recursive Fibonacci recomputes the same argument in many separate branches, so distinct subproblems number about n while calls grow far faster.

Memoization pays only when the same subproblem recurs. A recursion that splits its input into disjoint parts produces a distinct key on every call, so every lookup misses and you pay memory plus bookkeeping for zero saved work.

A cheapest itinerary's prefix must itself be cheapest: swapping in a cheaper A-to-M portion would make the whole cheaper, contradicting optimality. The argument needs fares to add across the cut and the two portions to be independent.

Passing cases shows only that no input you happened to choose exposed the flaw. Greedy optimality is a claim about every input, and it rests on the greedy-choice property: the locally best move must be consistent with some optimal solution.

The pieces are not independent: a longest simple path's prefix need not be longest to that town, and pasting two optimal halves can revisit a town, producing a walk that is not simple. Shortest paths suffer neither failure.

Memoization computes each distinct subproblem once and reuses the stored result, so cost drops from the number of call paths to (number of distinct states) times (work per transition). It only helps when subproblems actually repeat.

Both evaluate the same recurrence at the same asymptotic cost. Memoization recurses from the goal downward, caching answers on demand and touching only states it can reach. Tabulation fills every state in an order you choose, using no call stack.

Only the cells that a pending transition still reads have to stay in memory. When every value in row i is computed from row i-1 alone, the finished earlier rows are dead weight, so two rows are enough.

dp[0] is the empty-prefix answer: zero items considered, not the first item. Seed it with the identity of whatever the transition combines, such as 0 for a sum, 1 for counting the single empty arrangement, or a large sentinel for a minimisation. The first item's result lands in dp[1].

DP time is (number of states) times (cost of one transition), not table size alone. With nK cells and an inner scan of up to n predecessors, the cost is O(n^2K); counting cells hides the inner loop.

Every route into a cell takes its last step from either the cell above or the cell to its left. Those two sets of routes are disjoint and together cover every route, so the two counts simply add.

dp[i][w] is the best total value reachable using only the first i items within a capacity of w. The recurrence takes the larger of leaving item i out, dp[i-1][w], and taking it, value[i] + dp[i-1][w - weight[i]], when it fits.

dp[a] holds the fewest coins summing exactly to amount a: one plus the smallest dp[a - c] over each denomination c that fits. Amounts no combination reaches carry an infinity sentinel, never 0.

Greedy commits to a big slot before knowing what it blocks: taking a slot forbids both neighbours, so two merely good neighbours can outvalue one great slot. The take-or-skip recurrence best(i) = max(best(i-1), value(i) + best(i-2)) weighs both futures.

dp[i][j] is the edit distance between the first i characters of one name and the first j of the other — the indexes are prefix LENGTHS, not positions. Row 0 holds 0,1,2,...,j: turning nothing into a j-character prefix costs j insertions.