51. What steps do you follow to solve a dynamic programming problem?
MediumDynamic programming
Technical
Show model answer
1) Define the state: what does dp[i] (or dp[i][j]) mean? 2) Write the recurrence that builds a state from smaller ones. 3) Set base cases. 4) Choose an evaluation order (top-down with memoisation, or bottom-up). 5) Read the answer and optimise space if only recent rows are needed. Reconstruct the actual solution by storing choices or walking the table backwards.