Give every DP state a precise meaning

Write one sentence describing what the state represents. For example, say whether it describes the best cost for the first p items or the number of ways to reach a particular position. Then derive the recurrence from smaller states and list the base cases. If a transition needs information the state does not store, revise the state definition before coding.