Solves overlapping subproblems once and stores results.
DP solves problems with overlapping subproblems and optimal substructure by storing sub-results (memoisation or tabulation). Classics: Fibonacci, knapsack, longest common subsequence, edit distance, shortest paths. Define state, transition and base cases.
Fibonacci with memoisation drops from O(2ⁿ) to O(n).
Dynamic programming avoids repeating work when subproblems overlap, which turns exponential problems into practical ones.
Solves overlapping subproblems once and stores results.
Dynamic programming avoids repeating work when subproblems overlap, which turns exponential problems into practical ones.
Top-down memoisation stores results of recursive calls, while bottom-up tabulation fills a table from smaller subproblems.
Look for optimal substructure, where the best answer uses best answers to subproblems, and overlapping subproblems that repeat.
Typical applications include computing the cheapest way to split a cutting stock into pieces, finding the edit distance between two spelling words and choosing a sequence of jobs that maximises profit subject to time limits.
Study "Minimum spanning trees" first (topic 28 of 104 in Software & Computing). It covers the groundwork this topic builds on.
Top-down vs bottom-up. State space size. Space optimisation.
Fibonacci with memoisation drops from O(2ⁿ) to O(n).
The next topic is "Greedy algorithms", which builds directly on this one.
It is classed as Beginner in Software & Computing (topic 29 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.
Want to practise? Open the interactive course for quick checks, quizzes, simulations and progress tracking.