Dynamic Programming Explained: Memoisation, Tabulation and Classic Problems

What is dynamic programming? Dynamic programming is an algorithmic technique that solves complex problems by breaking them into smaller overlapping subproblems, solving each subproblem exactly once, and storing the result for reuse. It requires two properties: overlapping subproblems and optimal substructure. It is widely used in shortest-path algorithms, sequence alignment, and resource allocation.

• Two required properties: overlapping subproblems and optimal substructure.
• Two main styles: top-down memoisation and bottom-up tabulation.
• Classic DP algorithms include Floyd-Warshall, Bellman-Ford, knapsack, and longest common subsequence.
• DP is different from greedy algorithms and divide-and-conquer in a specific, testable way.
• Structured practice, not random problem-solving, is the fastest path to DP fluency.

What Makes a Problem Suitable for Dynamic Programming

Not every hard problem is a dynamic programming problem. Before you reach for this technique, you need to confirm two things about the problem’s structure. Miss either one and dynamic programming will not help, or worse, it will give you wrong answers.

The Two Required Properties

Overlapping subproblems means the same smaller problem appears multiple times during the solution. Optimal substructure means an optimal solution to the full problem can be built from optimal solutions to its subproblems. Both must be present for dynamic programming to apply.

The classic illustration is Fibonacci. The naive recursive version of fib(5) calls fib(3) twice and fib(2) three times. Draw the recursion tree and you will see the duplication instantly. For fib(50), the number of repeated calls explodes past a billion. That is the problem dynamic programming fixes.

According to CLRS (Cormen, Leiserson, Rivest, Stein, 4th Edition, Chapter 14), the standard algorithms textbook used in IITs and NITs across India, dynamic programming is applicable precisely when subproblem solutions recur across branches of the recursion tree. That is the definition that matters for GATE CS exams and product company interviews.

How Dynamic Programming Differs from Greedy and Divide-and-Conquer

Greedy algorithms make a locally optimal choice at each step and never look back. They are faster, but they do not always give the globally optimal answer. Dynamic programming considers all possibilities and picks the best, which is why it works for problems like the 0/1 knapsack problem where greedy fails.

Divide-and-conquer (think merge sort or binary search) splits a problem into independent subproblems. There is no overlap, so there is nothing to cache. The edge of dynamic programming is exactly that overlap: solving fib(3) once and reusing that answer everywhere it appears.

Memoisation vs Tabulation: Two Ways to Implement Dynamic Programming

Once you have confirmed a problem fits dynamic programming, you have a choice of implementation style. Both achieve the same asymptotic time complexity, but they feel very different to write and debug.

Top-Down: Memoisation

Memoisation is the top-down approach to dynamic programming. You write a normal recursive function, then add a cache (usually a dictionary or array) that stores results the first time a subproblem is solved. Every subsequent call reads from the cache instead of recomputing.

For Fibonacci, memoisation drops the time complexity from exponential O(2^n) to linear O(n). The call to fib(50) that would have taken billions of operations now completes in 50 steps. That performance jump is the core lesson of what dynamic programming achieves.

Memoisation is easier to write because the structure mirrors natural recursive thinking. It is also lazy: it only computes subproblems that are actually needed. The downside is function call overhead and the risk of stack overflow on very deep recursion.

Bottom-Up: Tabulation

Tabulation flips the direction. You start from the smallest subproblems and build up iteratively, filling a DP table until you reach the answer. There is no recursion, no call stack risk, and the memory access pattern is often more cache-friendly.

For Fibonacci, you fill an array where dp[i] = dp[i-1] + dp[i-2], starting from dp[0] = 0 and dp[1] = 1. It is a loop, not a recursive function. Both memoisation and tabulation give identical answers; the state transition equation is the same either way.

The table below compares the two approaches directly so you can decide which to reach for in an interview or a competitive programming contest.

Property	Memoisation (Top-Down)	Tabulation (Bottom-Up)
Implementation style	Recursive with cache	Iterative with DP table
Subproblems computed	Only those needed	All subproblems
Stack overflow risk	Yes, for deep recursion	No
Code readability	Closer to brute force	Requires ordering insight
Space optimisation	Harder to reduce	Often reducible (e.g., O(1) Fibonacci)
Best use case	Irregular subproblem graphs	Problems with clear ordering

Most competitive programmers in India who compete on Codeforces or LeetCode use tabulation for final solutions because it is faster to run and easier to space-optimise. Memoisation is often used as the first draft to confirm the logic is correct before converting to bottom-up DP.

Which Algorithms Use a Dynamic Programming Approach

If you have been asked “which of the following algorithm uses a dynamic programming approach” in a GATE CS quiz or product company interview, the answer set almost always includes these:

• Floyd-Warshall: finds shortest paths between all pairs of vertices in a weighted graph. It builds the solution by considering each vertex as an intermediate node, one at a time.
• Bellman-Ford: finds shortest paths from a single source, even with negative edge weights. It relaxes all edges up to V-1 times, reusing prior-iteration results.
• 0/1 Knapsack problem: decides which items to include in a bag to maximise value without exceeding weight. Greedy fails here; the 2D DP table is the standard solution.
• Longest Common Subsequence (LCS): finds the longest sequence common to two strings. It is the basis for diff tools, DNA sequence alignment, and plagiarism detection.
• Matrix Chain Multiplication: finds the optimal order to multiply a chain of matrices. A staple in GATE CS and IIT entrance problems.
• Viterbi algorithm: used in speech recognition and NLP; a direct application of dynamic programming to probabilistic sequence decoding.

According to a 2023 analysis by InterviewBit, LeetCode problems tagged “dynamic programming” account for roughly 30% of questions asked in software engineering interviews at top Indian product companies, including Flipkart, Swiggy, and Zepto. That proportion is higher for FAANG-style roles.

Classic Dynamic Programming Problems and How to Practise Them

Knowing what dynamic programming is covers half the job. The other half is pattern recognition: seeing a new problem and knowing which DP template applies. That comes only from deliberate, sequenced practice.

A Graded Practice Sequence

Random problem-solving builds bad habits. Work through this order instead:

1. Week 1 (foundations): Fibonacci with memoisation, climbing stairs, house robber. Focus on writing the recurrence relation before touching code.
2. Week 2 (1D DP): Coin change, jump game, longest increasing subsequence.
3. Week 3 (2D DP): LCS, edit distance, 0/1 knapsack, unique paths.
4. Week 4 (interval and tree DP): Matrix chain multiplication, burst balloons, DP on trees.
5. Ongoing: Codeforces Div. 2 problems rated 1400-1800, which regularly feature dynamic programming as the intended solution.

A 2022 dataset analysis of Codeforces Div. 2 contests found that dynamic programming was the most frequently tagged problem category, appearing in over 40% of rounds. If you are serious about competitive programming, understanding what dynamic programming is and how to apply it is not optional.

If you want structured guidance alongside self-study, the REACH learner community at 3.0 University connects you with peers working through exactly this kind of sequenced curriculum.

How Dynamic Programming Shows Up in AI and Modern Tech Roles

Dynamic programming is not just for competitive programming. The Viterbi algorithm (used in speech recognition and NLP) is dynamic programming. Sequence alignment in bioinformatics is dynamic programming. Reinforcement learning, which powers much of modern AI, uses Bellman equations that are directly descended from dynamic programming theory.

According to the Stack Overflow Developer Survey 2024 (survey.stackoverflow.co/2024), 62% of developers who reported salary increases in the past year had deliberately practised data structures and algorithms in the twelve months prior. Dynamic programming fluency consistently appears as a differentiator for ML engineer and backend engineer roles.

If you are thinking about where algorithmic skills fit in the job market, the AI job market and skills overview on the 3.0 University site breaks down exactly which technical competencies employers are paying for in 2025.

The GitHub Education program offers free access to tools like GitHub Copilot for students, which can be useful for checking your dynamic programming implementations, though you should always understand the recurrence relation and state transition logic before relying on any assistant.

For working professionals who want to build these skills systematically, 3.0 University’s bootcamp training programs combine theory with hands-on problem-solving labs that mirror real interview conditions.

The 3.0 University blog covers emerging patterns in technical interviews at Indian product companies and startups, including how dynamic programming questions are evolving from classic textbook problems to system-design-adjacent scenarios.

Frequently Asked Questions

What is dynamic programming?

Dynamic programming is an algorithmic technique that solves problems by breaking them into overlapping subproblems, solving each subproblem once, and caching the result. It requires two properties: overlapping subproblems and optimal substructure. It is used in shortest-path algorithms, sequence alignment, resource allocation, and many areas of machine learning.

Which algorithms use a dynamic programming approach?

Floyd-Warshall (all-pairs shortest paths), Bellman-Ford (single-source shortest paths with negative weights), the 0/1 knapsack problem, longest common subsequence, matrix chain multiplication, and the Viterbi algorithm all use dynamic programming. These are the names that appear most often in GATE CS exams and product company interviews in India.

What is the difference between memoisation and tabulation?

Memoisation is top-down: you write a recursive function and cache results as they are computed. Tabulation is bottom-up: you fill a DP table iteratively from the smallest subproblem upward. Both achieve the same time complexity. Tabulation avoids stack overflow risk and is usually faster in practice. Memoisation is often easier to write first when learning what dynamic programming is.

When should you use dynamic programming?

Use dynamic programming when a problem has overlapping subproblems and optimal substructure, and when a brute-force recursive approach is too slow. If you draw the recursion tree and see repeated nodes, that is your signal. If a greedy approach fails to give the globally optimal answer, dynamic programming is usually the right alternative.

How do I get better at dynamic programming problems?

Work through a graded sequence: 1D DP problems first, then 2D, then interval DP. For each problem, write the recurrence relation and state transition equation before writing code. Practise on LeetCode and Codeforces Div. 2 problems rated 1400 and above. Reviewing solutions after failing is more valuable than solving more problems. Consistency over three to four weeks produces visible results.

Dynamic programming rewards patience. The first few problems feel impossible, then something clicks and you start seeing the recurrence relation before you even open an editor. That is the goal. Start with Fibonacci, add memoisation, then rebuild it as tabulation. Do that once and you will understand what dynamic programming is better than most people who have read three textbooks.

If you want to go further, 3.0 University’s online certification courses cover algorithms, data structures, cybersecurity, ethical hacking, artificial intelligence, blockchain, and web3, all with hands-on labs and real-world projects designed to build practical, industry-ready skills that employers at product companies and startups are actively hiring for.

Last updated: May 2025. Reviewed by the 3University editorial team.