State Representation and Transitions

A state must summarize everything the future needs

A DP state is sufficient only if two histories with the same state have identical future possibilities. Omitting a constraint can merge histories that require different answers.

For selecting nonadjacent study rewards, define best[i] as the maximum reward from the first i days. The transition is max(best[i-1], best[i-2]+reward[i-1]). The first option skips the newest day; the second takes it and excludes its neighbor.

Copy codefun bestReward(rewards: IntArray): Long {
    var twoBack = 0L
    var oneBack = 0L
    for (reward in rewards) {
        val current = maxOf(oneBack, twoBack + reward)
        twoBack = oneBack
        oneBack = current
    }
    return oneBack
}

Empty selection is allowed, so negative rewards can be skipped. If at least one day must be selected, the base cases and result policy change.

Exercise

Verify [2,7,9,3,1] gives twelve. Add a constraint allowing at most two selected days and explain why the original one-dimensional state is insufficient.

Check: derive new state dimensions from missing information rather than adding indexes without a semantic definition.

Further reading: Optimization models