Dynamic Programming21 sections · 916 units
Open in Course

Grid Paths - State Definition

What dp[i][j] means

Define dp[i][j] as the number of ways to reach cell (ii,jj) from (1,1). For blocked cells, dp[i][j] = 0. For passable cells, you can arrive from the cell above or from the left. The base case: dp[1][1] = 1 if it's passable, otherwise dp[1][1] = 0.

If you can't even start, there are no paths. The state must capture everything needed to solve the subproblem. If you are missing information, you cannot compute the answer correctly. If you include too much, your solution will be slow or use too much memory.