State & transition
Overview
The state is the minimal set of parameters that uniquely determines a subproblem's answer. The transition is the recurrence relation: how the answer for a state is built from the answers to smaller states.
Defining the state and transition is the practical checklist for designing any Dynamic Programming algorithm.
Where used: Every DP algorithm, Algorithm design interviews
Why learn this
- Tracing a given DP table is easy, but designing the state for a new problem is where most people freeze.
- Learning to define `dp[state]` in plain English is the single most important skill in Dynamic Programming.
Common mistakes
- Choosing a state that is too coarse: If your state loses information needed for the transition, you can't compute the answer. For example, in the knapsack problem, just tracking 'capacity left' isn't enough; you also need to track 'which item am I deciding on'.
- Choosing a state that is too fine: Including unnecessary variables in the state blows up the state space, making your algorithm use too much memory and time.
Recall questions
- What is the 'state' in Dynamic Programming?
- What is the 'transition' in Dynamic Programming?
- What are the four steps to design a DP solution?
Understanding checks
If you are trying to solve a problem where you need to maximize profit from buying and selling a stock once, what information must your state capture?
The state must capture the current day (index) and whether you currently hold a stock or not.
Without knowing if you hold a stock, you don't know if your valid next transition is 'sell' or 'buy'.
A student defines their state for the 0/1 Knapsack problem as `dp[w] = max value for capacity w`. What's wrong?
It is too coarse. It doesn't track which items have already been used, so the transition might use the same item multiple times.
0/1 Knapsack requires each item to be used at most once. The state must be `dp[i][w]` to track both the items considered so far and the remaining capacity.
Practice tasks
Define the state in code
Modify this naive climbing stairs function to take a `memo` dictionary. What should the key (state) be?
Challenge
Design a state
You are given a grid and can move right or down. You need to find a path that maximizes the sum of numbers collected, but you can only collect at most one negative number. Define the state.
Continue learning
Previous: Optimal substructure
Next: Memoization (top-down)
Next: Tabulation (bottom-up)