Dynamic Programming
5 lessonsAbout 30 minutesAdvanced
This part of the DSA Tutorial runs from Dynamic Programming Explained through to Bitmask Dynamic Programming. There are 5 lessons here, and working through them takes about 30 minutes at a steady pace.
It follows on from Union-Find, so finish that first if you have not already — the examples below assume you are comfortable with it.
Each lesson below says what it covers before you open it. Read them in order the first time; afterwards this page works as a index you can jump back into when you need to check one thing.
- 1Dynamic Programming ExplainedDynamic programming is recursion that stops repeating itself. Learn memoisation and tabulation in JavaScript, and the two conditions a problem must meet before DP applies.
- 2Classic DP ProblemsClimbing stairs, coin change, longest common subsequence and the knapsack — the four dynamic programming problems that most others are variations of, solved in JavaScript.
- 31D Dynamic ProgrammingOne-dimensional DP problems in JavaScript — house robber, longest increasing subsequence, word break — and how to recognise when a single array of state is enough.
- 42D Dynamic ProgrammingGrid paths, edit distance and 2D DP tables in JavaScript — when a problem needs two dimensions of state, and how to reduce the table to a single row.
- 5Bitmask Dynamic ProgrammingWhen the DP state is a set of visited items, store it as bits in an integer. Bitmask DP in JavaScript, with the travelling salesman problem as the worked example.