Quartz 4

9.0 Dynamic Programming

1 min read

Dynamic Programming

Captures overlapping subproblems and optimal substructure. Backbone of FAANG-hard problems.

1.0 1D DP

  1. Fibonacci, Climbing Stairs
  2. House Robber
  3. Coin Change

2.0 2D DP

  1. Longest common subsequence
  2. Edit Distance
  3. DP on grids

3.0 DP with States

  1. DP[i][j], DP[i][j][k] patterns
  2. Buy/sell stock with cooldowns
  3. Knapsack variations

4.0 DP with Choices and Backtracking

  1. Word Break
  2. Palindrome Partitioning
  3. Regex Matching

5.0 Bitmask DP

  1. Traveling salesman
  2. Set cover
  3. Subset state transitions

6.0 Optimized DP Patterns

  1. Space optimized DP
  2. Monotonic queue optimization
  3. Divide and conquer DP

Graph View

Backlinks