DP Tutorials

Basic Dynamic Programming

  1. Watch DP video by Errichto
  2. Read hackerearth article for DP
tip

Note: For visualising recursion tree of common problems like finding Fibonacci number, coin change problem, etc. you may use Recursion Tree Visualisation. Observe that DP can be applied only when there are overlapping subproblems.

2-D Dynamic Programming

  1. Read hackerearth article on 2-D Dynamic Programming
  2. Watch Video on "Coin change" (double counting) problem by Errichto
  3. Watch Video on "Line of wines" problem by Errichto

State Space Reduction

  1. Read hackerearth article on state space reduction
tip

You must take care of time limit and especially memory limit while using DP. Often problems are framed in such a way that it wants you to use your memory smartly.

Session slides

  1. Day 1 - Intuition for DP, Minimum coins, Fibonacci number, Longest Increasing Subsequence(LIS), Coin Change, Subset Sum Problem

  2. Day 2 - Staircase climbing problem and its variations, Basics of PnC, Wildcard Matching Problem

Additional Resources

  1. You can also learn from Digit DP, a technique used to solve problems from this article

  2. You can also go through this hackerrank article for many standard DP problems.

  3. A great lecture series of MIT for some standard problems of dynamic programming :

    Lecture 1 - Fibonacci and shortest paths

    Lecture 2 - Text Justification, Blackjack

    Lecture 3 - Parenthesization, Edit Distance, Knapsack

    Lecture 4 - Guitar Fingering, Tetris, Super Mario Bros

Edit this page