2D Dynamic Programming

Fill a 2D table where each cell depends on previously computed cells in two dimensions, covering pairs of sequences or grid paths.

Fill a 2D table where each cell depends on previously computed cells in two dimensions, covering pairs of sequences or grid paths.

dp[i][j] always holds the optimal answer for the subproblem over the first i elements of one dimension and the first j of another.

Each cell is computed exactly once from already-computed neighbours, reducing exponential recursion to O(m × n) time and space.

A simple fill order ensures every dependency is satisfied before it is needed.