State Transition Thinking

What Is State Transition Thinking?

State transition thinking is the systematic process of converting a problem into a DP solution by answering four questions in order.

THE FOUR QUESTIONS:
  1. STATE:       "What does dp[i] (or dp[i][j]) represent?"
  2. TRANSITION:  "How does dp[i] depend on smaller sub-problems?"
  3. BASE CASES:  "What are the smallest known answers?"
  4. ANSWER:      "Where in the table is the final answer?"

This isn't guesswork — it's a repeatable process.
Every DP problem follows this structure.
The difficulty is in DEFINING the state precisely.

Step 1: Defining the State

The state must encode exactly what you need to solve the sub-problem — no more, no less.

RULE: Given only the state variables, can you compute dp[state]?
  If YES → state is sufficient.
  If NO  → state is missing information — add another dimension.

COMMON STATE SHAPES:
  dp[i]        → "answer for the first i elements / up to position i"
  dp[i][j]     → "answer for elements i through j" (interval DP)
               → "answer for first i elements of s1 and j elements of s2"
  dp[i][w]     → "answer using first i items with w capacity used"
  dp[i][state] → "answer at position i with additional constraint state"

THE STATE MUST BE:
  Complete:    Contains all information needed for the sub-problem
  Minimal:     No unnecessary information (wastes memory if included)
  Consistent:  Same state values → same answer (no ambiguity)

BAD STATE EXAMPLE:
  Problem: Maximum sum of non-adjacent elements in array
  Bad state: dp[i] = "maximum sum using elements at even or odd positions"
    → Not linked to specific position i; ambiguous
  Good state: dp[i] = "maximum sum using elements from array[0..i]"
    → Clear: first i+1 elements; unambiguous answer

Step 2: Writing the Transition

The transition answers: how is dp[i] built from smaller sub-problems?

PROCESS:
  1. Enumerate all choices available at step i.
  2. For each choice, express the total result in terms of dp[smaller].
  3. Combine choices (usually max/min for optimisation, sum for counting).

CHOICE PATTERN:
  "At each step, I can do X or Y. If I do X, the result is f(dp[prev]).
   If I do Y, the result is g(dp[prev]). Take the best (or count all)."

OPTIMISATION (max/min):
  dp[i] = max(choice_1, choice_2, ..., choice_k)

COUNTING (number of ways):
  dp[i] = choice_1 + choice_2 + ... + choice_k

EXISTENCE (can I reach this state?):
  dp[i] = choice_1 OR choice_2 OR ... OR choice_k

Worked Example 1: Climbing Stairs

Problem: You can take 1 or 2 steps. How many distinct ways to reach step n?

STEP 1 — STATE:
  dp[i] = number of distinct ways to reach step i

STEP 2 — TRANSITION:
  Choices to reach step i:
    Choice A: arrive from step i-1 (took 1 step)  → dp[i-1] ways
    Choice B: arrive from step i-2 (took 2 steps) → dp[i-2] ways
  These are mutually exclusive → add:
  dp[i] = dp[i-1] + dp[i-2]

STEP 3 — BASE CASES:
  dp[0] = 1  (one way to stay at step 0: do nothing)
  dp[1] = 1  (one way: take one step)

STEP 4 — ANSWER:
  dp[n]

TRACE for n=5:
  dp[0]=1, dp[1]=1
  dp[2] = dp[1]+dp[0] = 2
  dp[3] = dp[2]+dp[1] = 3
  dp[4] = dp[3]+dp[2] = 5
  dp[5] = dp[4]+dp[3] = 8

Ways to climb 5 stairs = 8 ✓

Worked Example 2: House Robber

Problem: Rob houses in a row. Can't rob adjacent houses. Maximise total stolen.

STEP 1 — STATE:
  dp[i] = maximum money robbing houses from index 0 to i

STEP 2 — TRANSITION:
  At house i, two choices:
    Choice A: SKIP house i → best is whatever was optimal up to i-1
              → dp[i-1]
    Choice B: ROB house i  → must have skipped house i-1
              → dp[i-2] + nums[i]
  Take the maximum:
  dp[i] = max(dp[i-1], dp[i-2] + nums[i])

STEP 3 — BASE CASES:
  dp[0] = nums[0]           (only one house — rob it)
  dp[1] = max(nums[0], nums[1])  (two houses — rob the richer one)

STEP 4 — ANSWER:
  dp[n-1]

TRACE for nums = [2, 7, 9, 3, 1]:
  dp[0] = 2
  dp[1] = max(2,7) = 7
  dp[2] = max(dp[1], dp[0]+nums[2]) = max(7, 2+9) = 11
  dp[3] = max(dp[2], dp[1]+nums[3]) = max(11, 7+3) = 11
  dp[4] = max(dp[3], dp[2]+nums[4]) = max(11, 11+1) = 12

Maximum = 12 (rob houses 0+2+4: 2+9+1=12) ✓

Worked Example 3: Unique Paths (2D State)

Problem: Grid of m rows and n columns. Move only right or down. Count paths from top-left to bottom-right.

STEP 1 — STATE:
  dp[i][j] = number of distinct paths to reach cell (i, j)

STEP 2 — TRANSITION:
  Cell (i,j) can only be reached from:
    Above: (i-1, j) — took a down move
    Left:  (i, j-1) — took a right move
  All paths to (i,j) pass through exactly one of these two cells:
  dp[i][j] = dp[i-1][j] + dp[i][j-1]

STEP 3 — BASE CASES:
  First row: dp[0][j] = 1 for all j  (only one way: all right moves)
  First col: dp[i][0] = 1 for all i  (only one way: all down moves)

STEP 4 — ANSWER:
  dp[m-1][n-1]

TRACE for 3×3 grid:
  Initial:        After filling:
  [1, ?, ?]       [1, 1, 1]
  [1, ?, ?]  →    [1, 2, 3]
  [1, ?, ?]       [1, 3, 6]

  dp[1][1] = dp[0][1]+dp[1][0] = 1+1 = 2
  dp[1][2] = dp[0][2]+dp[1][1] = 1+2 = 3
  dp[2][1] = dp[1][1]+dp[2][0] = 2+1 = 3
  dp[2][2] = dp[1][2]+dp[2][1] = 3+3 = 6

Paths in 3×3 grid = 6 ✓

Worked Example 4: Min Cost Climbing Stairs

Problem: Each stair has a cost. Pay cost[i] to leave step i. Can step 1 or 2 steps. Minimise total cost to reach the top.

STEP 1 — STATE:
  dp[i] = minimum cost to REACH step i (before paying to leave)

STEP 2 — TRANSITION:
  To reach step i, came from step i-1 (paying cost[i-1]) or
  step i-2 (paying cost[i-2]):
  dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

STEP 3 — BASE CASES:
  dp[0] = 0  (start here for free)
  dp[1] = 0  (can also start here for free — problem allows both)

STEP 4 — ANSWER:
  dp[n]  (n = len(cost) = one past the last stair = the "top")

TRACE for cost = [10, 15, 20]:
  n=3 (top = index 3)
  dp[0]=0, dp[1]=0
  dp[2] = min(dp[1]+cost[1], dp[0]+cost[0]) = min(0+15, 0+10) = 10
  dp[3] = min(dp[2]+cost[2], dp[1]+cost[1]) = min(10+20, 0+15) = 15

Minimum cost = 15 (path: start at step 1, pay 15, jump 2 to top) ✓

Worked Example 5: Coin Change — Adding a Constraint Dimension

Problem: Given coin denominations and a target amount, find the minimum coins to make the amount.

STEP 1 — STATE:
  dp[i] = minimum coins needed to make amount i
  (The "amount" is both the sub-problem index AND the constraint)

STEP 2 — TRANSITION:
  To make amount i, use one coin of denomination c (for each c in coins):
    Remaining amount after using coin c: i - c
    Cost:                                1 + dp[i-c]
  Take the minimum over all valid coins:
  dp[i] = min(1 + dp[i-c]) for each c in coins where i-c >= 0

STEP 3 — BASE CASES:
  dp[0] = 0  (zero coins needed to make amount 0)
  dp[i] = ∞  for all i > 0 initially (not yet computed)

STEP 4 — ANSWER:
  dp[amount], or -1 if dp[amount] == ∞ (amount is unreachable)

TRACE for coins=[1,3,4], amount=6:
  dp[0]=0
  dp[1]: use 1 → 1+dp[0]=1.  dp[1]=1
  dp[2]: use 1 → 1+dp[1]=2.  dp[2]=2
  dp[3]: use 1 → 1+dp[2]=3; use 3 → 1+dp[0]=1.  dp[3]=1
  dp[4]: use 1 → 1+dp[3]=2; use 3 → 1+dp[1]=2; use 4 → 1+dp[0]=1.  dp[4]=1
  dp[5]: use 1 → 1+dp[4]=2; use 3 → 1+dp[2]=3; use 4 → 1+dp[1]=2.  dp[5]=2
  dp[6]: use 1 → 1+dp[5]=3; use 3 → 1+dp[3]=2; use 4 → 1+dp[2]=3.  dp[6]=2

Minimum coins for 6: 2 (3+3) ✓

Output:
Climb stairs(5):     8
House robber:        12
Unique paths(3,3):   6
Min cost stairs:     15
Coin change(6):      2

The State Sufficiency Test

Before writing a single line of code, verify your state definition is correct.

TEST: Can two different inputs produce the same state values
      but require different answers?

If YES  → state is INSUFFICIENT — add another dimension.
If NO   → state is complete — proceed to write transitions.

EXAMPLE — Insufficient state:
  Problem: Robot in a grid with obstacles; count paths from top-left to bottom-right.
  Attempt: dp[i] = "number of paths to row i"
  Test: two different columns in row i are both "at row i" but have different
        path counts based on their column position.
  → FAIL: state missing column info. Fix: dp[i][j].

EXAMPLE — Sufficient state:
  Problem: House Robber
  State: dp[i] = max money from houses 0..i
  Test: two different arrays might share the same dp[i] value,
        but that's fine — dp[i] just asks "what's the best we can do?"
        and the recurrence dp[i] = max(dp[i-1], dp[i-2]+nums[i]) 
        correctly uses the array value nums[i] at each step.
  → PASS: state is sufficient.

EXAMPLE — Missing constraint dimension:
  Problem: 0/1 Knapsack — items with weight/value, bag capacity W.
  Attempt: dp[i] = "max value using items 0..i"
  Test: dp[3] should be different if bag has 5kg left vs 10kg left.
        Same item index but different capacity → different answers.
  → FAIL: must add capacity as a dimension. Fix: dp[i][w].

When to Add a Dimension

ADD A DIMENSION WHEN:
  The same position/index can have different answers depending on
  some constraint or status that changes over time.

COMMON EXTRA DIMENSIONS:
  [i][j]:      two pointers / two strings / two sequences
  [i][0/1]:    binary state (holding/not, used/not, odd/even position)
  [i][k]:      at most k operations/transactions allowed
  [i][w]:      remaining capacity w
  [i][state]:  bitmask or small enumerated state

CLASSIC EXAMPLES:
  Best Time to Buy and Sell Stock II:
    dp[i][0] = max profit on day i, not holding stock
    dp[i][1] = max profit on day i, holding stock
    Binary state [0/1] captures "holding or not" which changes decisions.

  Best Time to Buy and Sell Stock III (at most 2 transactions):
    dp[i][k][0] and dp[i][k][1]
    where k = transactions used (0, 1, or 2).
    Three dimensions: day, transactions remaining, holding.

  Word Break:
    dp[i] = can string[0..i-1] be segmented into dictionary words?
    No extra dimension needed — the index i fully defines the sub-problem.

  Target Sum (assign + or - to each number, reach target):
    dp[i][s] = number of ways to assign signs to numbers 0..i-1 reaching sum s
    Sum s is the extra dimension — same index i, different reachable sums.

State Transition Patterns at a Glance

PATTERN          TRANSITION SHAPE              EXAMPLE
───────────────────────────────────────────────────────────────────
Linear 1-back    dp[i] = f(dp[i-1])            Prefix sums, cumulative max
Linear 2-back    dp[i] = f(dp[i-1], dp[i-2])  Fibonacci, Climbing Stairs
Choice at each   dp[i] = max(skip, take)        House Robber, Jump Game
2D grid          dp[i][j] = f(dp[i-1][j],      Unique Paths, Min Path Sum
                              dp[i][j-1])
Two sequences    dp[i][j] = f(dp[i-1][j-1],    LCS, Edit Distance
                              dp[i-1][j],
                              dp[i][j-1])
Knapsack         dp[i][w] = max(skip_item,      0/1 Knapsack, Coin Change
                               take_item)
Unbounded fill   dp[i] = min/max over all k     Coin Change, Word Break
                 choices: f(dp[i-k])
Interval         dp[i][j] = f(dp[i][k],         Matrix Chain, Burst Balloons
                              dp[k+1][j]) all k
Bitmask          dp[mask][i] = f(dp[mask ^ i])  TSP, Minimum XOR subset

Debugging a Wrong DP

SYSTEMATIC DEBUGGING STEPS:

1. PRINT THE TABLE — visualise dp[] for a small input.
   Does dp[i] represent what you intended?

2. CHECK BASE CASES — are dp[0], dp[1] correct?
   Manually verify by hand without using the recurrence.

3. VERIFY ONE TRANSITION — trace dp[2] by hand.
   Does the recurrence dp[2] = f(dp[1], dp[0]) give the right answer?

4. CHECK FILL ORDER — for dp[i][j], are dp[i-1][j] and dp[i][j-1]
   computed BEFORE dp[i][j]? Trace the loop order.

5. CHECK ANSWER LOCATION — is the final answer at dp[n], dp[n-1][m-1],
   or somewhere else?

6. CHECK SENTINEL VALUE — is the "infinity" sentinel large enough
   that `sentinel + cost` doesn't overflow?
   Use amount+1 or INT_MAX/2 instead of INT_MAX.

EXAMPLE BUG — Coin Change sentinel overflow:
  dp = [INT_MAX] * (amount+1)
  dp[i] = 1 + dp[i-c]   ← if dp[i-c] = INT_MAX, 1 + INT_MAX overflows!
  FIX: dp = [amount+1] * (amount+1)  ← sentinel = amount+1 (can't be valid answer)
       or check dp[i-c] != INT_MAX before relaxing.

The Transition Derivation Checklist

Before coding, answer these for your DP problem:

□ STATE:
    dp[___] = "___"
    (Fill in state variables and what the value represents)

□ TRANSITION:
    "At step ___, I have ___ choices:"
    "Choice 1: ___"  → dp[i] = f(dp[i-1])
    "Choice 2: ___"  → dp[i] = g(dp[i-2])
    "Combine by: max / min / sum"
    dp[i] = max/min/sum of all choices

□ BASE CASES:
    dp[0] = ___ (justify why)
    dp[1] = ___ (justify why)

□ ANSWER:
    "Final answer is at dp[___]"

□ FILL ORDER:
    "Must fill ___ before ___"
    (Outer loop: ___, Inner loop: ___)

□ SPACE OPTIMISATION:
    "dp[i] only depends on dp[___] and dp[___]"
    "Can reduce to ___ variables"

Common Mistakes

Confusing "skip" and "take" directions in the recurrence. In House Robber, dp[i] = max(dp[i-1], dp[i-2] + nums[i]): the first option dp[i-1] means "don't rob house i" (best up to i-1), and the second dp[i-2] + nums[i] means "rob house i" (skip i-1, add nums[i]). Swapping these — writing dp[i-2] for skip and dp[i-1] + nums[i] for take — gives wrong answers on adjacent houses.

State represents the wrong sub-problem boundary. "dp[i] = answer including element i" vs "dp[i] = answer for elements 0..i" are subtly different. The first is "answer ending at i" (used in LIS), the second is "answer using the best choice up to i" (used in House Robber). Choose based on what the recurrence needs.

Forgetting to handle the case where the transition doesn't apply. In Coin Change, dp[i] = min(1 + dp[i-c]) only applies when coin <= i. Without this check, accessing dp[i-c] at a negative index is undefined behaviour. Always guard transitions with validity checks.

Wrong base case for 2D problems. For Unique Paths, the entire first row and column must be 1 (not just dp[0][0]). Forgetting to initialise the full border causes 0s to propagate incorrectly through the table.

Off-by-one in the "top" of Min Cost Climbing Stairs. The target is index n (one past the last stair), not index n-1. Allocate dp[n+1] and return dp[n], not dp[n-1]. This is a common error when the problem says "reach the top" rather than "reach the last step."

Summary

State transition thinking converts a problem into a DP solution through four structured steps: define the state, write the transition, identify base cases, and determine the fill order.

The key insight in each step:

• ›State: dp[i] must be self-contained — given state values, the sub-problem answer is determined
• ›Transition: enumerate all choices at each step; combine with max, min, or sum
• ›Base cases: the anchors — smallest sub-problems answered directly, not via recurrence
• ›Fill order: dependencies before dependents — bottom-up fills in topological order

When to add dimensions:

• ›A constraint changes what choices are available → add it as a dimension (capacity, steps remaining, holding state)
• ›Same index, different valid answers depending on something → that "something" is a missing dimension

Five transition patterns covered:

• ›dp[i] = dp[i-1] + dp[i-2] — two prior states (Climbing Stairs)
• ›dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — binary choice (House Robber)
• ›dp[i][j] = dp[i-1][j] + dp[i][j-1] — two-direction 2D (Unique Paths)
• ›dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]) — cost-to-reach (Min Cost Stairs)
• ›dp[i] = min(1 + dp[i-c]) for all coins — unbounded choice set (Coin Change)

In the next topic you will explore Memoization — the top-down approach to DP, implementing recursive solutions with caching, handling the memo table, and converting recursive solutions to memoized ones step by step.