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