Micro-Drill #155 — 1D vs 2D DP: how to decide

1D vs 2D DP — DECISION TREE
────────────────────────────
Q: How many things change between subproblems?

ONE THING changes → 1D dp[i]
  "first i elements" or "up to value i"
  Examples: climbing stairs, house robber,
            word break, decode ways, coin change

TWO THINGS change → 2D dp[i][j]
  Patterns:
  ┌─ Two sequences → dp[i][j] = first i of seq1, j of seq2
  │  LCS, edit distance, regex matching
  ├─ Interval → dp[i][j] = substring s[i..j]
  │  Palindrome, matrix chain, burst balloons
  ├─ Index + capacity → dp[i][w] = first i items, weight w
  │  Knapsack, subset sum
  └─ Index + state → dp[i][s] = at position i in state s
     Stock problems, paint house

SHORTCUT: if problem has two input arrays/strings → 2D
          if problem says "capacity" or "limit" → 2D