Track 16 · Lesson 10 of 12

Dynamic programming

Solve problems built from overlapping subproblems by computing each subproblem once — top-down with a memo or bottom-up with a table.

You will be able to

• Recognise overlapping subproblems and describe a problem with a recurrence
• Turn a recurrence into a memoised recursive function or a bottom-up table
• Solve counting and minimum-cost problems such as climbing stairs and fewest coins
• Compute the longest common subsequence of two short sequences with a 2-D table