Dynamic Programming for Data Structures and Algorithmss
Dynamic programming, or DP, solves problems by breaking them into overlapping subproblems and storing each result so it is computed once. The unit covers recognising DP, top-down memoisation and bottom-up tabulation, and classic patterns such as knapsack, longest common subsequence, grid paths and coin change.
Stage: Advanced · Part of the Data Structures and Algorithms roadmap · Last reviewed 19 November 2026
What to learn in Dynamic Programming
- Define the state and recurrence for a DP problem before coding
- Convert a recursive solution to memoisation and then to a table
- Solve coin change and climbing stairs with one-dimensional DP
- Solve longest common subsequence with a two-dimensional table
- Reduce space by keeping only the previous row
Dynamic Programming interview questions
How do you recognise a dynamic programming problem?
Look for optimal substructure, where the best answer is built from best answers to smaller pieces, and overlapping subproblems, where the same piece recurs. Phrases like minimum cost, number of ways or longest sequence are common hints.
What is the difference between memoisation and tabulation?
Memoisation is top-down: recursion with a cache that stores results as they are first computed. Tabulation is bottom-up: you fill a table in dependency order iteratively. Both give the same complexity, but tabulation avoids recursion depth limits.
Where Dynamic Programming fits in the Data Structures and Algorithms roadmap
Dynamic Programming belongs to the Advanced stage (advanced level), which takes about 32 hours. Optimisation.
Other units in this stage
Back to the full Data Structures and Algorithms roadmap