Dynamic Programming
Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for 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 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.
Tabulation vs Memoization
There are two different ways to store the values so that the values of a sub-problem can be reused. Here, will discuss two patterns of solving dynamic programming (DP) problem:
- Tabulation: Bottom Up
- Memoization: Top Down
Tabulation
As the name itself suggests starting from the bottom and accumulating answers to the top. Let’s discuss in terms of state transition.
Let’s describe a state for our DP problem to be dp[x] with dp[0] as base state and dp[n] as our destination state. So, we need to find the value of destination state i.e dp[n].
If we start our transition from our base state i.e dp[0] and follow our state transition relation to reach our destination state dp[n], we call it the Bottom-Up approach as it is quite clear that we started our transition from the bottom base state and reached the topmost desired state.
Now, Why do we call it tabulation method?
To know this let’s first write some code to calculate the factorial of a number using bottom up approach. Once, again as our general procedure to solve a DP we first define a state. In this case, we define a state as dp[x], where dp[x] is to find the factorial of x.
Now, it is quite obvious that dp[x+1] = dp[x] * (x+1)
# Tabulated version to find factorial x.
dp = [0]*MAXN
# base case
dp[0] = 1;
for i in range(n+1):
dp[i] = dp[i-1] * i
Memoization
Once, again let’s describe it in terms of state transition. If we need to find the value for some state say dp[n] and instead of starting from the base state that i.e dp[0] we ask our answer from the states that can reach the destination state dp[n] following the state transition relation, then it is the top-down fashion of DP.
Here, we start our journey from the top most destination state and compute its answer by taking in count the values of states that can reach the destination state, till we reach the bottom-most base state.
Once again, let’s write the code for the factorial problem in the top-down fashion
# Memoized version to find factorial x.
# To speed up we store the values
# of calculated states
# initialized to -1
dp[0]*MAXN
# return fact x!
def solve(x):
if (x==0)
return 1
if (dp[x]!=-1)
return dp[x]
return (dp[x] = x * solve(x-1))
More articles on Dynamic Programming
Learn DSA with Python | Python Data Structures and Algorithms
This tutorial is a beginner-friendly guide for learning data structures and algorithms using Python. In this article, we will discuss the in-built data structures such as lists, tuples, dictionaries, etc, and some user-defined data structures such as linked lists, trees, graphs, etc, and traversal as well as searching and sorting algorithms with the help of good and well-explained examples and practice questions.
Contact Us