How to solve Dynamic Programming problems through Example?
Problem: Let’s find the Fibonacci sequence up to the nth term. A Fibonacci series is the sequence of numbers in which each number is the sum of the two preceding ones. For example, 0, 1, 1, 2, 3, and so on. Here, each number is the sum of the two preceding numbers.
Naive Approach: The basic way to find the nth Fibonacci number is to use recursion.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <iostream> using namespace std; // Function to find nth fibonacci number int fib(int n) { if (n <= 1) { return n; } int x = fib(n - 1); int y = fib(n - 2); return x + y; } // Drivers code int main() { int n = 5; // Function Call cout << fib(n); return 0; } |
Java
// Java code for the above approach: import java.io.*; class GFG { // Function to find nth fibonacci number public static int fib(int n) { if (n <= 1) { return n; } int x = fib(n - 1); int y = fib(n - 2); return x + y; } // Driver Code public static void main(String[] args) { int n = 5; // Function Call System.out.print(fib(n)); } } // This code is contributed by Rohit Pradhan |
Python3
# Function to find nth fibonacci number def fib(n): if (n <= 1): return n x = fib(n - 1) y = fib(n - 2) return x + y n = 5; # Function Call print(fib(n)) #contributed by akashish__ |
C#
using System; public class GFG { // Function to find nth fibonacci number public static int fib(int n) { if (n <= 1) { return n; } int x = fib(n - 1); int y = fib(n - 2); return x + y; } static public void Main() { int n = 5; // Function Call Console.WriteLine(fib(n)); } } // contributed by akashish__ |
Javascript
// Function to find nth fibonacci number function fib(n) { if (n <= 1) { return n; } let x = fib(n - 1); let y = fib(n - 2); return x + y; } // Drivers code let n = 5; // Function Call console.log(fib(n)); // This code is contributed by akashish__ |
Output
5
Complexity Analysis:
Time Complexity: O(2n)
- Here, for every n, we are required to make a recursive call to fib(n – 1) and fib(n – 2). For fib(n – 1), we will again make the recursive call to fib(n – 2) and fib(n – 3). Similarly, for fib(n – 2), recursive calls are made on fib(n – 3) and fib(n – 4) until we reach the base case.
- During each recursive call, we perform constant work(k) (adding previous outputs to obtain the current output). We perform 2nK work at every level (where n = 0, 1, 2, …). Since n is the number of calls needed to reach 1, we are performing 2n-1k at the final level. Total work can be calculated as:
- If we draw the recursion tree of the Fibonacci recursion then we found the maximum height of the tree will be n and hence the space complexity of the Fibonacci recursion will be O(n).
Efficient approach: As it is a very terrible complexity(Exponential), thus we need to optimize it with an efficient method. (Memoization)
Let’s look at the example below for finding the 5th Fibonacci number.
Representation of 5th Fibonacci number
Observations:
- The entire program repeats recursive calls. As in the above figure, for calculating fib(4), we need the value of fib(3) (first recursive call over fib(3)), and for calculating fib(5), we again need the value of fib(3)(second similar recursive call over fib(3)).
- Both of these recursive calls are shown above in the outlining circle.
- Similarly, there are many others for which we are repeating the recursive calls.
- Recursion generally involves repeated recursive calls, which increases the program’s time complexity.
- By storing the output of previously encountered values (preferably in arrays, as these can be traversed and extracted most efficiently), we can overcome this problem. The next time we make a recursive call over these values, we will use their already stored outputs instead of calculating them all over again.
- In this way, we can improve the performance of our code. Memoization is the process of storing each recursive call’s output for later use, preventing the code from calculating it again.
Way to memoize: To achieve this in our example we will simply take an answer array initialized to -1. As we make a recursive call, we will first check if the value stored in the answer array corresponding to that position is -1. The value -1 indicates that we haven’t calculated it yet and have to recursively compute it. The output must be stored in the answer array so that, next time, if the same value is encountered, it can be directly used from the answer array.
Now in this process of memoization, considering the above Fibonacci numbers example, it can be observed that the total number of unique calls will be at most (n + 1) only.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <iostream> using namespace std; // Helper Function int fibo_helper(int n, int* ans) { // Base case if (n <= 1) { return n; } // To check if output already exists if (ans[n] != -1) { return ans[n]; } // Calculate output int x = fibo_helper(n - 1, ans); int y = fibo_helper(n - 2, ans); // Saving the output for future use ans[n] = x + y; // Returning the final output return ans[n]; } int fibo(int n) { int* ans = new int[n + 1]; // Initializing with -1 for (int i = 0; i <= n; i++) { ans[i] = -1; } fibo_helper(n, ans); } // Drivers code int main() { int n = 5; // Function Call cout << fibo(n); return 0; } |
Java
// Java code for the above approach: import java.io.*; class GFG { // Helper Function public static int fibo_helper(int n, int ans[]) { // Base case if (n <= 1) { return n; } // To check if output already exists if (ans[n] != -1) { return ans[n]; } // Calculate output int x = fibo_helper(n - 1, ans); int y = fibo_helper(n - 2, ans); // Saving the output for future use ans[n] = x + y; // Returning the final output return ans[n]; } public static int fibo(int n) { int ans[] = new int[n + 1]; // Initializing with -1 for (int i = 0; i <= n; i++) { ans[i] = -1; } return fibo_helper(n, ans); } // Driver Code public static void main(String[] args) { int n = 5; // Function Call System.out.print(fibo(n)); } } // This code is contributed by Rohit Pradhan |
Python3
# Helper Function def fibo_helper(n, ans): # Base case if (n <= 1): return n # To check if output already exists if (ans[n] is not -1): return ans[n] # Calculate output x = fibo_helper(n - 1, ans) y = fibo_helper(n - 2, ans) # Saving the output for future use ans[n] = x + y # Returning the final output return ans[n] def fibo(n): ans = [-1]*(n+1) # Initializing with -1 #for (i = 0; i <= n; i++) { for i in range(0,n+1): ans[i] = -1 return fibo_helper(n, ans) # Code n = 5 # Function Call print(fibo(n)) # contributed by akashish__ |
C#
using System; public class GFG { // Helper Function public static int fibo_helper(int n, int[] ans) { // Base case if (n <= 1) { return n; } // To check if output already exists if (ans[n] != -1) { return ans[n]; } // Calculate output int x = fibo_helper(n - 1, ans); int y = fibo_helper(n - 2, ans); // Saving the output for future use ans[n] = x + y; // Returning the final output return ans[n]; } public static int fibo(int n) { int[] ans = new int[n + 1]; // Initializing with -1 for (int i = 0; i <= n; i++) { ans[i] = -1; } return fibo_helper(n, ans); } static public void Main() { // Code int n = 5; // Function Call Console.WriteLine(fibo(n)); } } // contributed by akashish__ |
Javascript
<script> // Javascript code for the above approach: // Helper Function function fibo_helper(n, ans) { // Base case if (n <= 1) { return n; } // To check if output already exists if (ans[n] != -1) { return ans[n]; } // Calculate output let x = fibo_helper(n - 1, ans); let y = fibo_helper(n - 2, ans); // Saving the output for future use ans[n] = x + y; // Returning the final output return ans[n]; } function fibo(n) { let ans = []; // Initializing with -1 for (let i = 0; i <= n; i++) { ans.push(-1); } return fibo_helper(n, ans); } // Drivers code let n = 5; // Function Call console.log(fibo(n)); // contributed by akashish__ </script> |
Output
5
Complexity analysis:
- Time complexity: O(n)
- Auxiliary Space: O(n)
Optimized approach: Following a bottom-up approach to reach the desired index. This approach of converting recursion into iteration is known as Dynamic programming(DP).
Observations:
- Finally, what we do is recursively call each response index field and calculate its value using previously saved outputs.
- Recursive calls terminate via the base case, which means we are already aware of the answers which should be stored in the base case indexes.
- In the case of Fibonacci numbers, these indices are 0 and 1 as f(ib0) = 0 and f(ib1) = 1. So we can directly assign these two values into our answer array and then use them to calculate f(ib2), which is f(ib1) + f(ib0), and so on for each subsequent index.
- This can easily be done iteratively by running a loop from i = (2 to n). Finally, we get our answer at the 5th index of the array because we already know that the ith index contains the answer to the ith value.
- Simply, we first try to find out the dependence of the current value on previous values and then use them to calculate our new value. Now, we are looking for those values which do not depend on other values, which means they are independent(base case values, since these, are the smallest problems
which we are already aware of).
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <iostream> using namespace std; // Function for calculating the nth // Fibonacci number int fibo(int n) { int* ans = new int[n + 1]; // Storing the independent values in the // answer array ans[0] = 0; ans[1] = 1; // Using the bottom-up approach for (int i = 2; i <= n; i++) { ans[i] = ans[i - 1] + ans[i - 2]; } // Returning the final index return ans[n]; } // Drivers code int main() { int n = 5; // Function Call cout << fibo(n); return 0; } |
Java
// Java code for the above approach: import java.io.*; class GFG { // Function for calculating the nth // Fibonacci number public static int fibo(int n) { int ans[] = new int[n + 1]; // Storing the independent values in the // answer array ans[0] = 0; ans[1] = 1; // Using the bottom-up approach for (int i = 2; i <= n; i++) { ans[i] = ans[i - 1] + ans[i - 2]; } // Returning the final index return ans[n]; } // Driver Code public static void main(String[] args) { int n = 5; // Function Call System.out.print(fibo(n)); } } // This code is contributed by Rohit Pradhan |
Python3
# Python3 code for the above approach: # Function for calculating the nth # Fibonacci number def fibo(n): ans = [None] * (n + 1) # Storing the independent values in the # answer array ans[0] = 0 ans[1] = 1 # Using the bottom-up approach for i in range(2,n+1): ans[i] = ans[i - 1] + ans[i - 2] # Returning the final index return ans[n] # Drivers code n = 5 # Function Call print(fibo(n)) #contributed by akashish__ |
C#
// C# code for the above approach: using System; public class GFG { // Function for calculating the nth // Fibonacci number public static int fibo(int n) { int[] ans = new int[n + 1]; // Storing the independent values in the // answer array ans[0] = 0; ans[1] = 1; // Using the bottom-up approach for (int i = 2; i <= n; i++) { ans[i] = ans[i - 1] + ans[i - 2]; } // Returning the final index return ans[n]; } static public void Main() { // Code int n = 5; // Function Call Console.Write(fibo(n)); } } // This code is contributed by lokeshmvs21. |
Javascript
<script> // Javascript code for the above approach: // Function for calculating the nth // Fibonacci number function fibo(n) { let ans = new Array(n + 1).fill(0); // Storing the independent values in the // answer array ans[0] = 0; ans[1] = 1; // Using the bottom-up approach for (let i = 2; i <= n; i++) { ans[i] = ans[i - 1] + ans[i - 2]; } // Returning the final index return ans[n]; } // Drivers code let n = 5; // Function Call console.log(fibo(n)); // contributed by akashish__ </script> |
Output
5
Complexity analysis:
- Time complexity: O(n)
- Auxiliary Space: O(n)
Optimization of above method
- in above code we can see that the current state of any fibonacci number depend only on prev two number
- so using this observation we can conclude that we did not need to store the whole table of size n but instead of that we can only store the prev two values
- so this way we can optimize the space complexity in the above code O(n) to O(1)
C++
// C++ code for the above approach: #include <iostream> using namespace std; // Function for calculating the nth Fibonacci number int fibo(int n) { int prevPrev, prev, curr; // Storing the independent values prevPrev = 0; prev = 1; curr = 1; // Using the bottom-up approach for (int i = 2; i <= n; i++) { curr = prev + prevPrev; prevPrev = prev; prev = curr; } // Returning the final answer return curr; } // Drivers code int main() { int n = 5; // Function Call cout << fibo(n); return 0; } |
Java
// C++ code for the above approach public class Main { // Function for calculating the nth Fibonacci number public static int fibo(int n) { int prevPrev, prev, curr; // Storing the independent values prevPrev = 0; prev = 1; curr = 1; // Using the bottom-up approach for (int i = 2; i <= n; i++) { curr = prev + prevPrev; prevPrev = prev; prev = curr; } // Returning the final answer return curr; } // Drivers code public static void main(String[] args) { int n = 5; // Function Call System.out.println(fibo(n)); } } |
Python3
# Python code for the above approach # Function for calculating the nth Fibonacci number def fibo(n): prevPrev, prev, curr = 0, 1, 1 # Using the bottom-up approach for i in range(2, n+1): curr = prev + prevPrev prevPrev = prev prev = curr # Returning the final answer return curr # Drivers code n = 5# Function Call print(fibo(n)) |
C#
using System; public class Program { // Function for calculating the nth Fibonacci number static int Fibo(int n) { int prevPrev, prev, curr; // Storing the independent values prevPrev = 0; prev = 1; curr = 1; // Using the bottom-up approach for (int i = 2; i <= n; i++) { curr = prev + prevPrev; prevPrev = prev; prev = curr; } // Returning the final answer return curr; } // Drivers code static void Main() { int n = 5; // Function Call Console.WriteLine(Fibo(n)); } } // This code is contributed by divyansh2212 |
Javascript
// Function for calculating the nth Fibonacci number function fibo(n) { let prevPrev = 0, prev = 1, curr = 1; // Using the bottom-up approach for (let i = 2; i <= n; i++) { curr = prev + prevPrev; prevPrev = prev; prev = curr; } // Returning the final answer return curr; } // Drivers code let n = 5; // Function Call console.log(fibo(n)); |
Output
5
Dynamic Programming (DP) Tutorial with Problems
Dynamic Programming (DP) is defined as a technique that solves some particular type of problems in Polynomial Time. Dynamic Programming solutions are faster than the exponential brute method and can be easily proved their correctness.
Important Topics in Dynamic Programming Tutorial
- Characteristics of Dynamic Programming Algorithm:
- What is the difference between a Dynamic programming algorithm and recursion?
- Techniques to solve Dynamic Programming Problems:
- Tabulation(Dynamic Programming) vs Memoization:
- How to solve a Dynamic Programming Problem?
- How to solve Dynamic Programming problems through Example?
- Greedy approach vs Dynamic programming
- Some commonly asked problems in Dynamic programming:
- FAQs about Dynamic Programming Algorithm:
Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for the same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.
Introduction to Dynamic Programming – Data Structures and Algorithm Tutorials
Contact Us