the DP transition

Once you know what a state is, the transition is the rule that tells you how to compute one state's answer from the answers of smaller states. It is the verb of a dynamic program: states are the nouns you store, the transition is what links them. Usually it has the flavor 'to solve this state, consider every first choice I could make, solve the residual subproblem each choice leaves behind, and take the best (or sum, or count) over those choices.' Writing the transition correctly is writing the recurrence, and it is justified by optimal substructure.

Mechanically, the transition expresses dp[state] in terms of dp[smaller states] plus the immediate cost or value of the choice connecting them. For the 0/1 knapsack, the transition at item i with capacity w is: dp[i][w] = max( dp[i-1][w], value[i] + dp[i-1][w - weight[i]] ), where the first branch skips item i and the second takes it (only allowed if weight[i] <= w). Read it aloud: the best value using the first i items is the better of not taking item i (so you still have all w for the first i-1 items) and taking it (gaining its value but spending its weight, leaving w - weight[i] for the rest). Each branch is itself an optimal sub-answer — that is optimal substructure in action.

The transition also fixes the cost of your DP, because the work to evaluate one state is the number of choices you consider in its transition. A 0/1 knapsack transition does O(1) work per state across O(nW) states, so O(nW) total. A transition that loops over O(n) predecessors (as in the simple longest-increasing-subsequence recurrence) costs O(n) per state across n states, so O(n^2). The honest caution: a transition is only correct if the subproblems it references are genuinely independent given the state — if two branches could secretly interfere (sharing a resource the state does not track), the recurrence is wrong even though it looks plausible.