Skip to main content

Pattern 13: Counting DP

The Combinatorial Pattern: Count number of ways to achieve a goal rather than finding optimal solution. Sum instead of min/max.

The Core Pattern​

THE MENTAL MODEL

Imagine counting all possible paths through a maze:

  1. Instead of finding best solution, count all solutions
  2. Use addition to combine counts from subproblems
  3. dp[i] = "number of ways to reach state i"
  4. Answer is sum of ways, not min/max
  5. Watch for overflow - use modulo

This is Counting DP.

Pattern Recognition​

WHEN YOU SEE THIS PATTERN

Keywords: "number of ways", "count", "how many", "combinations", "modulo 10^9+7"

Structure:

  • Need to count solutions, not optimize
  • Multiple ways to reach each state
  • Combine by addition

State:

  • dp[i] = "number of ways to reach/achieve state i"

Transitions:

  • Add ways from all possible previous states
  • dp[i] = dp[j1] + dp[j2] + ... + dp[jk]

Common Problems​

  • Climbing Stairs (count ways)
  • Unique Paths (count paths)
  • Coin Change 2 (count combinations)
  • Number of Dice Rolls with Target Sum
  • Target Sum (count ways)
  • Decode Ways
  • Knight Probability

(Example problems will be added here)