InternshipDynamic programming
Save the answers to smaller problems instead of repeating them.
If a recursive solution solves the same smaller problem many times, store each answer. That simple change can turn exponential time into linear time.
Expected output
8
That counts the ways to climb n stairs taking 1 or 2 steps at a time. Each answer depends only on the previous two.
0/1 knapsack
Expected output
9
Going backwards through capacity stops an item being used twice.