Correctness Property

Optimal Substructure

DP works because the best answer to a larger state can be composed from best answers to smaller states. Here, each grid cell’s optimal count comes from the two optimal neighbors.

MeaningBest builds from best

ExampleGrid DP

Global Objective

The target state asks for the full answer (bottom-right cell).

Valid Composition

Each cell’s answer is built from optimal answers of its top/left neighbors.

DP Table

dp[r][c] = dp[r-1][c] + dp[r][c-1]

0,01

0,10

0,20

0,30

0,40

1,00

1,10

1,20

1,30

1,40

2,00

2,10

2,20

2,30

2,40

3,00

3,10

3,20

3,30

3,40

Local Composition

top0

left0

dp[r][c]1

Loading Lab...