Dynamic Programming

Build optimal answers incrementally from smaller states and repeated substructure.

Build optimal answers incrementally from smaller states and repeated substructure.

The carried value always represents the best answer achievable ending at the current position while scanning forward.

Each state is computed once and reused — eliminating redundant work in overlapping subproblems.

The optimal answer at each step is fully determined by the previous state, so a single forward pass suffices.