Dynamic Programming (DP)

Dynamic Programming (DP) was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.

 

DP is an algorithm technique that is closely related to the divide and conquer approach. However, while the divide and conquer approach is essentially recursive, and so "top down", dynamic programming works "bottom up".

 

This method is an optimisation approach that transforms a complex problem into a sequence of simpler problems. It creates an array of related but simpler sub-problems, and then, it computes the solution to the big complicated problem by using the solution to the easier sub-problems which are stored in the array. In this way, the efficiency of the CPU can be enhanced.

 

DP solutions have a polynomial complexity which assures a much faster running time than other techniques like backtracking, brute-force etc. For example, the following simple recursive solution (top down) for Fibonacci Numbers gets exponential time complexity.

int fib (int n) {
    if (n <= 1)
    	return n;
    return fib(n - 1) + fib(n - 2);
}

The time complexity reduces to linear in the below-optimised code (bottom up).

std::vector<int> f{0, 1};
for (int i = 2; i <= n; ++i) {
	f.emplace_back(f[i - 1] + f[i - 2]);
}
return f[n];

DP works by storing the result of sub-problems so that when their solutions are required, they are at hand and we do not need to recalculate them. The technique of storing the results of already solved sub-problems is called memoisation. By saving the values in the array, we save time for computations of sub-problems we have already come across.