Dynamic Programming21 sections · 916 units
Open in Course

The Same Four Steps

Pattern reminder

The four-step pattern you learned still applies:

1.1. Define the state. What does dp[i][j]dp[i][j] represent? Write it in plain English.

2.2. Find the transition. How does dp[i][j]dp[i][j] relate to smaller subproblems?

3.3. Set the base cases. What are the simplest subproblems you can answer directly?

4.4. Extract the answer. Which cell (or combination of cells) gives the final answer? Nothing changes except you have more indices. If you can do 1D (one-dimensional) DP, you can do 2D (two-dimensional) DP.