Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure. More so than the optimization techniques described previously, dynamic programming provides a general framework for analyzing many problem types.
The origin of the term dynamic programming has very little to do with writing code. It was first coined by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. Back then programming meant “planning,” and “dynamic programming” was conceived to optimally plan multistage processes.
Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for the same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.
For example, if we write a simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.
Dynamic programming has applications in mathematical optimization, computational complexity theory, and computer programming. When an algorithm is broken down such that the runtime is most efficient, it is in its optimal substructure.
7 Steps to solve a Dynamic Programming problem
Greedy algorithms look for locally optimum solutions or in other words, a greedy choice, in the hopes of finding a global optimum. Hence greedy algorithms can make a guess that looks optimum at the time but becomes costly down the line and does not guarantee a globally optimum
In contrast to greedy algorithms, where local optimization is addressed, dynamic algorithms are motivated by the overall optimization of the problem.
In contrast, divide and conquer algorithms, where solutions are combined to achieve an overall solution, dynamic algorithms use the output of a smaller sub-problem and then try to optimize a bigger sub-problem. Dynamic algorithms use Memoization to remember the output of already solved sub-problems.
Dynamic programming is a technique for solving problems recursively. It can be implemented by memoization or tabulation.
Memoization refers to the technique of caching and reusing previously computed results. It is a top-down approach where we just start by solving the problem in a natural manner and storing the solutions of the sub-problems along the way.
The main idea behind Memoization was to reuse already calculated sub-problem results in order to solve the original problem.
Tabulation is a bottom-up method for solving DP problems. It starts from the base cases and finds the optimal solutions to the problems whose immediate sub-problems are the base cases. Then, it goes one level up and combines the solutions it previously obtained to construct the optimal solutions to more complex problems.
Eventually, tabulation combines the solutions of the original problem’s subproblems and finds its optimal solution.
| Memoization | Tabulation |
| State transition relation is easy to create. | In tabulation, the state transition is difficult to create. |
| Code is not complicated and it's not difficult to create. | Code becomes difficult when lots of conditions are needed. |
| It is slow because lots of recursive calls and return statements are required. | It is fast as the result of the previously solved sub-problems can be directly accessed from the table. |
| In a memoized version, entries in the table are filled on demand. | In a tabulated version, all the entries must be filled one by one. |
Fibonacci series without recording the results of the subproblems.
# Fibonacci Series using Recursion
def fib(n):
if (n <= 1):
return n
return fib(n - 1) + fib(n - 2)
Time Complexity: O(2n)
Auxiliary Space: O(n) The extra space is used due to the recursion call stack.
# a program for Memoized version of nth Fibonacci number
def fib(n, lookup):
if n <= 1:
lookup[n] = n
# if the value is not calculated previously then calculate it
if lookup[n] is None:
lookup[n] = fib(n-1, lookup) + fib(n-2, lookup)
return lookup[n]
Time Complexity: O(N)
Auxiliary Space: O(N) The extra space is used due to the recursion call stack.
Tabulation (Bottom Up):
# Python program Tabulated (bottom up) version
def fib(n):
f = [0] * (n + 1)
f[1] = 1
# calculating the fibonacci and storing the values
for i in xrange(2, n + 1): # xrange() in Python 2
f[i] = f[i - 1] + f[i - 2]
return f[n]
xrange() : This function returns the generator object that can be used to display numbers only by looping. The only particular range is displayed on demand and hence called “lazy evaluation“.
Time Complexity: O(N)
Auxiliary Space: O(N) The extra space is used due to the recursion call stack.
Applications of dynamic programming
Dynamic programming can be used in both top-down and bottom-up manners. And of course, most of the time, referring to the previous solution output is cheaper than recomputing in terms of CPU cycles.
