My dynamic programming journey [1] – Fib with memorization

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

#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;
}

#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:

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)

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.

Tech Blog of Edward