State Transition Modeling from Problem Stories

Turn story into variables with ranges—document types, dimensions, caps—then prove transitions cover all cases.

Why this shows up in the real world

Logistics models trucks (capacity, time) as DP dimensions. Sports stamina as extra axis.

Core idea (explained for students)

Write a transition table on paper: rows current state, columns action, cell next state.

Try this in Python

def model_two_dim(W: int, T: int, items: list[tuple[int, int, int]]) -> int:
    # weight, time, value
    dp = [[0] * (T + 1) for _ in range(W + 1)]
    for wt, tm, val in items:
        for w in range(W, wt - 1, -1):
            for t in range(T, tm - 1, -1):
                dp[w][t] = max(dp[w][t], dp[w - wt][t - tm] + val)
    return dp[W][T]


print(model_two_dim(10, 5, [(2, 1, 5), (3, 2, 8), (4, 3, 10)]))

Common mistakes

• Undefined behavior for illegal actions—should be zero ways or -inf cost.
• Implicit constraints (non-decreasing) not encoded.

Key takeaways

• Enumerate illegal tuples explicitly in code comments.