If we want to understand the true essence of dynamic programming, we should consider the simple example of fibonacci series. Using the conventional algorithm the time complexity of the solution is O(2^n).

def fibonacci(n):
i, a, b = 1, 0, 1
while(i<=n):
a, b = b, a+b
i += 1
return b

But using the dynamic programming we can reduce the function call, as well as the time complexity to O(n).

class Main {
int[] f = new int[100];
public int fibonacci(int n) {
f[0] = f[1] = 1;
for(int i=2;i<=n;i++) {
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
}

### Like this:

Like Loading...