WORLD 5

DYNAMIC PROGRAMMING

Remember the answers to smaller problems and build up: a staircase, a row of houses, a pile of coins, a rising run, two words.

STAGE 0 Dynamic programming tutorial

0:00 / 0:00

The move

Never solve the same subproblem twice. Either save each answer as you recurse (memoization) or fill a table from the smallest case up, building each cell once from the cells before it.

Spot it
The problem asks for a count, a best (min or max), or a yes or no, and the answer for n depends on answers for smaller sizes.
Cost
Number of states times the work per state: n states with constant work each is O(n) time.

17 STAGES Dynamic programming problems

☆☆☆☆☆ Clear 5 to finish this world.