State Transition in Dynamic Programming: The Process from Problem to State Transition Equation

Dynamic Programming (DP) is a common method for solving complex problems. It improves efficiency by breaking down problems, storing intermediate results, and avoiding redundant calculations. “State transition” is the core of dynamic programming, describing how states in different stages of a problem interact and derive from each other. For beginners, understanding how to derive the state transition equation step by step from the problem itself is key to mastering dynamic programming.

I. Core Ideas of Dynamic Programming and State Transition¶

Dynamic programming is typically used to solve problems with overlapping subproblems and optimal substructure, such as the Fibonacci sequence, climbing stairs, and coin change. Its core lies in: breaking down complex problems into simpler subproblems, storing solutions to subproblems (i.e., “states”) to avoid redundant calculations, and ultimately deriving the solution to the original problem.

State transition is the “bridge” connecting these subproblem solutions. It describes: how the current state is derived from one or more previous states.

II. Steps from Problem to State Transition Equation (Example: Climbing Stairs)¶

Let’s take the “climbing stairs problem” as a concrete example to break down the process of deriving the state transition equation:

Problem: Suppose you need to climb n stairs, and you can climb 1 or 2 stairs at a time. How many different ways are there?

Step 1: Clarify the Problem and Identify Subproblems¶

To solve for the number of ways to climb n stairs:
- The last step can only be climbing 1 stair from step n-1 or 2 stairs from step n-2 (optimal substructure).
- Thus, the number of ways = the number of ways to reach step n-1 + the number of ways to reach step n-2 (overlapping subproblems, e.g., for n=3, n-1=2 and n-2=1 will be recalculated).

Step 2: Define the State¶

Let dp[i] represent the number of ways to reach the i-th stair.
- dp[i] is a quantitative description of the “i-th stair” stage, the core we need to compute.

Step 3: Derive the State Transition Equation¶

From Step 1, the number of ways to reach the i-th stair is the sum of two cases:
- Climbing 1 stair from i-1: dp[i-1] ways;
- Climbing 2 stairs from i-2: dp[i-2] ways.

Thus, the state transition equation is:
dp[i] = dp[i-1] + dp[i-2]

Step 4: Determine Initial Conditions and Boundaries¶

State transitions need “starting points” (basic state values):
- dp[0] = 1 (Define “0 stairs” as 1 way, serving as the recursion starting point);
- dp[1] = 1 (Only 1 way to climb 1 stair: climb directly 1 step).

Step 5: Calculate the Result¶

With the transition equation and initial conditions, we can compute step-by-step:
- dp[2] = dp[1] + dp[0] = 1 + 1 = 2 (2 stairs: 1+1 or 2);
- dp[3] = dp[2] + dp[1] = 2 + 1 = 3 (3 stairs: 1+1+1, 1+2, 2+1);
- In general, dp[n] gives the number of ways to climb n stairs.

III. Another Example: Coin Change Problem (Extension)¶

Problem: Given coin denominations [1,2,5] and a total amount n, find the minimum number of coins needed to sum to n. If it’s impossible, return -1.

Step 1: Define the State¶

Let dp[i] represent the minimum number of coins needed to sum to amount i.

Step 2: Derive the Transition Equation¶

To sum to amount i, the last coin used can be any denomination coin. Thus, the remaining amount is i - coin, and:
dp[i] = min(dp[i - coin] + 1) (if i >= coin and dp[i - coin] is valid).

Step 3: Initial Conditions¶

• dp[0] = 0 (No coins needed for amount 0);
• Other amounts are initialized to infinity (indicating “not reachable”).

Step 4: Calculate the Result (Example: n=5)¶

• dp[0] = 0;
• dp[1] = dp[0] + 1 = 1 (1 coin of 1);
• dp[2] = min(dp[1] + 1, dp[0] + 1) = 1 (1 coin of 2);
• dp[5] = min(dp[4] + 1, dp[3] + 1, dp[0] + 1) = 1 (1 coin of 5).

IV. Key Summary for Beginners¶

1. Define the state first: Use dp[i] to clearly describe the problem stage (e.g., “summing to amount i” or “reaching stair i”).
2. Transition equation is the core: Analyze “how to reach the current state in the last step” to find state dependencies (e.g., dp[i] = dp[i-1] + dp[i-2]).
3. Initial conditions are essential: Start from the most basic state values (e.g., dp[0]) to avoid errors during derivation.
4. Practice regularly: Familiarize yourself with state transition thinking through problems like climbing stairs, coin change, and the longest increasing subsequence.

The essence of dynamic programming is “trading space for time” by storing intermediate results to avoid redundant calculations. The state transition equation is the bridge connecting these results. By mastering the three-step method of “defining states → finding transition relationships → writing equations,” you can gradually overcome the core of dynamic programming!