Skip to main content
HTML5ANDCSS3 logoHTML5ANDCSS3Tools and Tutorials

Dynamic Programming

4 lessonsAbout 24 minutesAdvanced

This part of the DSA Tutorial runs from Dynamic Programming Explained through to 2D Dynamic Programming. There are 4 lessons here, and working through them takes about 24 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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.
All of DSA TutorialNext: Greedy