It is rather complicated to consider the advance level of dynamic programming at the beginning, so I have decided to start with a basic example: finding Fibonacci numbers.
Since the concepts of recursion and memorization are often required in dynamic programming, therefore, I have implemented a version of memorization.
- Set base case of 0 and 1 equal to 1
- Check if
fib(n)already exist in the array - If yes, return it directly
- If no, return it as
fib(n-1)+fib(n-2)like ordinary approach
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include<bits/stdc++.h> using namespace std; int fib(int n, vector<int>&mem){ printf("fib(%d)\n", n); int res = 0; if(n == 0 || n == 1) return 1; if(mem[n] != -1){ printf("Using fib(%d)\n", n); return mem[n]; } else{ mem[n] = fib(n-1, mem) + fib(n-2, mem); //printf("fib(%d) = %d saved \n", n, res); } return mem[n]; } int main(){ int n = 10; vector<int> mem (n + 1, -1); printf("Ans = %d\n", fib(n, mem)); return 0; } |
Console output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
fib(10) fib(9) fib(8) fib(7) fib(6) fib(5) fib(4) fib(3) fib(2) fib(1) fib(0) fib(1) fib(2) Using fib(2) fib(3) Using fib(3) fib(4) Using fib(4) fib(5) Using fib(5) fib(6) Using fib(6) fib(7) Using fib(7) fib(8) Using fib(8) |
It can be observed that starting from fib(2), we have obtained the result and store it into the table, which give O(1) future access time.