A recurrence describes how the answer to one state depends on answers to smaller or earlier states.
It is the rule that gives dynamic programming its structure.
Core Idea
Before choosing memoization or tabulation, the algorithm needs a recurrence. The recurrence says what value should be computed for each state.
For example, if dp[i] is the number of ways to reach step i, then dp[i] = dp[i - 1] + dp[i - 2] when each move can climb one or two steps.
Python Example
def climb_stairs(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] += dp[i - 1]
if i >= 2:
dp[i] += dp[i - 2]
return dp[n]The recurrence adds ways from the previous one-step and two-step positions.
Common Confusions
A recurrence is not the table itself. The table stores values. The recurrence defines how values are related.
The state must be clear before the recurrence can be clear. dp[i] needs a precise meaning.
When To Use It
Use recurrence thinking whenever an answer can be built from smaller answers, especially in dynamic programming, recursion, counting, and optimization problems.