Dynamic Programming Examples

Dynamic Programming Beginner’s Tutorial

Dynamic Programming

Dynamic programming is a method for solving a complex problem by breaking it down into simpler subproblems, solving each of those subproblems just once, and storing their solutions – in an array(usually).

Now, every time the same sub-problem occurs, instead of recomputing its solution, the previously calculated solutions are used, thereby saving computation time at the expense of storage space.

Dynamic programming can be implemented in two ways –

  • Memoization
  • Tabulation

Memoization – Memoization uses the top-down technique to solve the problem i.e. it begin with original problem then breaks it into sub-problems and solve these sub-problems in the same way.

In this approach, you assume that you have already computed all subproblems. You typically perform a recursive call (or some iterative equivalent) from the main problem. You ensure that the recursive call never recomputes a subproblem because you cache the results, and thus duplicate sub-problems are not recomputed.

Tabulation – Tabulation is the typical Dynamic Programming approach. Tabulation uses the bottom-up approach to solve the problem, i.e., by solving all related sub-problems first, typically by storing the results in an array. Based on the results stored in the array, the solution to the “top” / original problem is then computed.


Memoization and tabulation are both storage techniques applied to avoid recomputation of a subproblem

Example – Consider a program to generate Nth fibonacci number

Solution 1 – using top-down approach without Dynamic Programming

  2. int Fib(int n) 
  3. { 
  4.      if(n<=1) 
  5.      { 
  6.           return n; 
  7.      } 
  8.      else 
  9.      { 
  10.           return (fibonacci(n-1)+fibonacci(n-2)); 
  11.      } 
  12. }

Solution 2 – using top-down approach with Memoization (Dynamic Programming)

  1. int memoize[]; 
  2. //method to initialize memoize array to -1 
  4. void initialize() 
  5. { 
  6. 	... 
  7. } 
  9. int Fib(int n) 
  10. { 
  11. 	if(memoize[n]==-1) 
  12. 	{ 
  13. 		//means the solution is not yet calculated 
  14. 		if(n<=1) 
  15. 		{ 
  16. 			memoize[n]=1; 
  17. 		} 
  19. 		else 
  20. 		{ 
  21. 			memoize[n]=Fib[n-1]+Fib[n-2]; 
  22. 		} 
  23. 	} 
  24. 	return memoize[n]; 
  25. }

Solution 3 – Bottom up Dynamic Programming

  1. int table[N]; 
  2. void setup_fib() 
  3. { 
  4.     table[0] = 1; 
  5.     table[1] = 1; 
  7.     for (int i = 2; i < N; i++) 
  8.         table[i] = table[i-1] + table[i-2]; 
  9. } 
  11. int Fib(int x)  
  12. {  
  13. 	return table[x];  
  14. }

The idea behind dynamic programming, In general, is to solve a given problem, by solving different parts of the problem (subproblems), then using the cached solutions of the subproblems to reach an overall solution.


The problems that can be solved by using Dynamic Programming has the following two main properties-

  1. Overlapping sub-problems
  2. Optimal Substructure

1) Overlapping Subproblems:

Overlapping subproblems is a property in which a problem can be broken down into subproblems which are used multiple times.

Dynamic Programming is mainly used when solutions of same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a array so that these don’t have to recomputed. So Dynamic Programming is not useful when there are no overlapping subproblems because there is no point storing the solutions if they are not needed again.

2) Optimal substructure
Optimal substructure is a property in which an optimal solution of the original problem can be constructed efficiently from the optimal solutions of its sub-problems.


If a given problem obey both these properties, then the problem can be solved by using Dynamic Programming.

Steps to follow for solving a DP problem –

  1. Express a solution mathematically
  2. Express a solution recursively
  3. Either develop a bottom up algorithm or top-down memoized algorithm

Here’s the List of Dynamic Programming Problems and their Solutions

Kadane’s Algorithm
0 1 Knapsack Problem
Longest Increasing Subsequence Problem
Edit Distance Problem
Integer Knapsack Problem
Fibonacci Numbers Problem
Rod Cutting Problem
Subset Sum Problem
Parentheses Expressions Problem – Catalan numbers
Forming Triangles Problem
Change Making Problem
Coin Change Problem
Number of Ways to Reach a Given Score Problem
Matrix Chain Multiplication Problem
Maximum Value of Gifts Problem
Rod Cutting – Maximum Product Problem
Stolen Values Problem
Assembly Line Scheduling
Shortest Common Subsequence Problem
Boredom Problem
Longest Common Subsequence Problem
Binary Trees with N Keys Problem
Balanced Partition Problem
Box Stacking Problem
Building Bridges
Dice Throw Problem
Longest Substring Without Duplication Problem
Optimal Game Strategy Problem
Minimum Number of Jumps Problem
Binomial Coefficients Problem
Counting Boolean Parenthesization Problem
Building Problem
Longest Common Substring Problem
Longest Palindromic Subsequence Problem
Make Palindrome Problem
Minimum number of Squares Problem
Sum of Digits Problem
Candies Distribution Problem Problem
Mixtures Problem
Blueberries Problem
Army Problem
Double Helix Problem
Length of the Longest Arithmetic Progression Problem
Newspaper Headline Problem
Stock Market Problem
Treats for the Cows
Weighted Activity Selection Problem
Assignments Problem
Bellman Ford Algorithm
Bytelandian Gold Coins Problem
Cut Ribbon Problem
Flloyd Warshall Algorithm
Non Decreasing Digits Problem
T-Primes Problem
Trigraphs Problem

Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.