Dynamic Programming21 sections · 916 units
Open in Course

Vocabulary - 2D State

Two parameters

A 2D (two-dimensional) DP state uses two indices: dp[i][j]dp[i][j]. Each combination of ii and jj represents a unique smaller problem to solve. For example, dp[3][5]dp[3][5] might mean "the answer when you've processed 33 items and used weight 5." You can think of it as a table. Rows are one dimension, columns are another.

Each cell stores the answer to one specific subproblem. The base cases initialize some cells (often dp[0][0]dp[0][0] or the first row/column), and the final answer comes from a specific cell or a combination of cells.