Paul's Python CoursePPC

Dynamic programming

Not met yet

Dynamic programming solves a problem from the answers to smaller versions of it, and works each smaller answer out only once. If a recursion keeps asking the same questions, either cache the answers as they come (memoisation) or fill a table on purpose, smallest first, so every slot's ingredients are ready when it needs them. The answers don't change, only the work: 27,457 calls for making 50p become 338. Counting change, fewest coins, edit distance and packing a van are all tables.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks a recursion that tries every coin as the next coin counts each handful once, when it counts every order of the same coins.
  • Thinks storing answers in a cache or table can change what a function gives back, rather than only how much work it does.
  • Thinks a table's slots can be filled in any order, when each slot needs the smaller ones it's built from to be filled first.
  • Thinks always taking the biggest coin that fits gives the fewest coins, whatever the coins are.

Where it comes up