Dynamic Programming

Dynamic Programming is an incredibly confusing topic when you first start, it is good to try recognizing commonly occurring patterns to reduce the amount of head scratching you do

Recognizing DP problems

  1. 1.
    Minimizing/maximizing:
  2. 2.
    Number of ways:
  3. 3.

Steps to solving DP

  1. 1.
    Identify states
  2. 2.
    Identify state transitions
  3. 3.
    Implement top-down
  4. 4.
    Convert to bottom-up

Types of DP

  1. 1.
    Linear sequence
  2. 2.
    Grid
  3. 3.
    Two sequences

Common recurrence relations

Recursive to iterative

Optimizing space