counting DP
Most introductory DP optimizes something — the shortest path, the maximum value, the fewest coins. Counting DP instead answers 'how many?': how many ways to tile a board, how many paths through a grid, how many strings avoid a forbidden pattern. The structure is the same as optimization DP, but the operation that combines subproblems changes. Where an optimization DP takes a min or a max over choices, a counting DP takes a SUM, because the number of ways to do a thing is the sum of the numbers of ways to do each mutually exclusive first step.
The bridge from optimization to counting rests on two combinatorial rules. The addition rule: if a final outcome can be reached through several disjoint cases, its count is the sum of the cases' counts — this is why transitions add. The multiplication rule: if a construction is an independent first part followed by an independent second part, the count is the product of the two parts' counts. So a counting transition typically looks like dp[state] = sum over each valid previous-state of dp[previous-state] (times a multiplicity factor if a step has several independent sub-choices). For example, counting paths in a grid that only move right or down: dp[i][j] = dp[i-1][j] + dp[i][j-1], because every path into cell (i, j) arrives either from above or from the left, and those two sets of paths are disjoint, so you add them. The base case dp[0][0] = 1 says there is exactly one empty way to be at the start.
Counting DP has the same time and space cost as the corresponding optimization DP — the only change is +/sum replacing min/max — so it inherits whatever speed-ups (prefix sums, etc.) the structure allows. Two honest cautions specific to counting. First, the counts can grow astronomically (often exponentially), so answers are usually requested modulo a prime like 10^9 + 7, and you must reduce as you go to avoid overflow. Second, correctness hinges on the cases being truly disjoint and exhaustive: if two different ways of decomposing a state can produce the SAME object, you double-count; if some objects fit no case, you under-count. Getting the partition exactly right — every object counted once and only once — is the real subtlety of counting DP.
Number of ways to climb n stairs taking 1 or 2 steps at a time: dp[k] = dp[k-1] + dp[k-2], because the last move is either a single step (from k-1) or a double step (from k-2), and those are disjoint. dp[0]=1, dp[1]=1, so dp[2]=2, dp[3]=3, dp[4]=5 — the Fibonacci numbers, by exactly the addition rule.
Counting DP replaces min/max with sum over disjoint, exhaustive cases.
Sum only over cases that are both disjoint (no object counted twice) and exhaustive (no object missed); a subtle overlap silently double-counts. And reduce modulo the required prime as you add, or huge counts overflow.