Skip to interview prep
Apexed

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.

What steps do you follow to solve a dynamic programming problem — Data structures & algorithms interview question — Apexed