If you’re learning Python, it can be hard to take that step from writing sample code to efficient code. As you progress in skill, program runtime efficiency becomes more and more important, acting as a key indicator of success in coding interviews and later real-world solutions.
One way to get more efficiency out of your recursive programs is to start using dynamic programming, a time-saving storage-based technique, in place of brute force recursion. Dynamic programming uses the principle of optimality, which is the idea that if all steps of a process are optimized, then the result is also optimized. In our case, the optimal step is the one that takes the least amount of time which in programming means it takes the fewest new computations.
To help you jump into efficient Python code, here’s a quick tutorial on what dynamic programming is, why it’s more efficient, and how to use it to solve common interview problems.
Here’s what we’ll cover today
- What is Dynamic Programming?
- Why is Dynamic Programming efficient?
- Bottom-Up Dynamic Programming
- Top-down Dynamic Programming
- Dynamic Programming Examples
- Practice Dynamic Programming Problems
- What to Learn Next
What is Dynamic Programming?
Dynamic programming is a problem-solving technique for resolving complex problems by recursively breaking them up into sub-problems, which are then each solved individually. Dynamic programming optimizes recursive programming and saves us the time of re-computing inputs later.
This differs from the Divide and Conquer technique in that sub-problems in dynamic programming solutions are overlapping, so some of the same identical steps needed to solve one sub-problem are also needed for other sub-problems.
This leads us to the main advantage of dynamic programming. Instead of recomputing these shared steps, dynamic programming allows us to simply store the results of each step the first time and reuse it each subsequent time.
Note:
Dynamic programming is a special case of the larger category of recursive programming, however not all recursive cases can use dynamic programming
Why is Dynamic Programming efficient? Recursion vs. DP
If the two are so closely entwined, why is dynamic programming favored whenever possible? This is because brute force recursive programs often repeat work when faced with overlapping steps, spending unneeded time and resources in the process.
Dynamic programming solves this issue by ensuring each identical step is only completed once, storing that step’s results in a collector such as a hash table or an array to call whenever it’s needed again. In doing so, dynamic programming allows for less repeated work and, therefore, better runtime efficiency.
Note:
Dynamic programming essentially trades space efficiency for time efficiency as solution storage requires space not used in brute force recursive solutions.
Dynamic Programming Examples
Real-world Dynamic Programing
Unlike computers, memory-based processes like dynamic programming are intuitive to humans.
Consider this real-world example:
Imagine you want to go to a new grocery store a few streets away, but you don’t know how to get there. To solve the sub-problem of the route to the store, you look up directions on your smartphone’s map and then make your way there.
If you thought in a recursive fashion, each time you wanted to go to the store, you’d have to take the time to look up the directions again.
Instead, we naturally think dynamically, remembering the directions to the store from when we first looked them up. As a result, we don’t need to spend time looking them up when we go in the future.
This is, in essence, how dynamic programming functions in programs as well.
Factorial Problem
We can see in real life how dynamic programming is more efficient than recursion, but let’s see it in action with Python code!
Below we have two solutions that both find the Fibonacci number of a given input and then show a graph of the program’s runtime. One is simple brute force recursion, and the other instead uses dynamic programming.
Look at the difference:
Dynamic Programming:
import time
import matplotlib.pyplot as plt
calculated = {}
def fib(n):
if n == 0: # base case 1
return 0
if n == 1: # base case 2
return 1
elif n in calculated:
return calculated[n]
else: # recursive step
calculated[n] = fib(n-1) + fib(n-2)
return calculated[n]
showNumbers = False
numbers = 20
Recursion:
import time
import matplotlib.pyplot as plt
def fib(n):
if n <= 0: # base case 1
return 0
if n <= 1: # base case 2
return 1
else: # recursive step
return fib(n-1) + fib(n-2)
numbers = 20
As you can see, in the code of the dynamic solution we’ve added the ability to store old results (line 12) before moving onto the next recursive step (lines 13 - 15). We’ll see more complex dynamic solutions and their step-by-step breakdowns later in the article.
Bottom-Up Dynamic Programming
Not all dynamic solutions work in the same way. Some are built bottom-up while others are built top-down. The distinction can be found in how each begins a problem and how sub-problem results are stored.
Bottom-up dynamic programming solutions start by looking at the smallest possible sub-problem, called the base case, and then works step-by-step up to each sub-problem. As each sub-problem is solved, its solution is saved and used to solve the next lowest sub-problem. In the end, these building solutions will lead to an answer to the main problem.
What is Tabulation?
Tabulation is the process of storing results of sub-problems from a bottom-up approach sequentially.
In tabulation, we don’t pick and choose which sub-problems need to be solved and instead solve every sub-problem between the base case and the main problem. This sequential order lends tabulation to use either lists or array, as those collections organize information in a specific order.
Note:
Tabulation is iterative, not recursive, as in tabulation we complete each sub-problem before beginning the next.
Top-down Dynamic Programming
Top-down dynamic programming is the opposite to bottom-up. A top-down solution first looks at the main problem and breaks it into smaller and smaller necessary sup-problems until the base case is reached. This is the most common way of building recursive solutions.
In using this style of recursive chain, top-down dynamic programming only solves sub-problems as they are needed rather than solving all in order.
What is Memoization?
Memoization is the process of storing sub-problem results in a top-down approach.
Since top-down approaches solve problems as needed, memoization must store data in a non-sequential way. This means hash tables are the best collection type, as they store data in an unordered way.
In Python, this is best accomplished using the dictionary data structure because we can use it to store unordered data with key/value pairs.
Dynamic Programming Examples: Bottom-up vs Top-down
To better understand the differences between these designs, let’s see how we’d rework our Fibonacci example in both a bottom-up and top-down way.
Bottom-up:
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
# table for tabulation
table = [None] * (n+1)
table[0] = 0 # base case 1, fib(0) = 0
table[1] = 1 # base case 2, fib(1) = 1
# filling up tabulation table starting from 2 and going upto n
for i in range(2,n+1):
# we have result of i-1 and i-2 available because these had been evaluated already
table[i] = table[i-1] + table[i-2]
# return the value of n in tabulation table
return table[n]
print(fib(100))
-->
354224848179261915075
Solution breakdown:
First, we created a list for the purpose of tabulation called table. We set its size equal to n+1 since we are going to evaluate n+1 total Fibonacci numbers (0,1,2...n). Next, we updated the value for the base cases in the table by setting 0th and 1st index to 0 and 1 respectively. The only thing left to do is iterate over the table to fill it up. At the end of the iteration, we will have the n^th Fibonacci number at the last index of the table.
Top-down:
memo = {} #dictionay for Memoization
def fib(n):
if n == 0: # base case 1
return 0
if n == 1: # base case 2
return 1
elif n in memo: # Check if result for n has already been evaluated
return memo[n] # return the result if it is available
else: # otherwise recursive step
memo[n] = fib(n-1) + fib(n-2) # store the result of n in memoization dictionary
return memo[n] # return the value
print (fib(100))
-->
354224848179261915075
Solution breakdown (Memoization):
The only changes we will make to our original Fibonacci algorithm is the addition and usage of this new dictionary. We have defined a dictionary globally, so it is available to all the fib() calls (line 1). Next, after the base cases, we check whether this number has already been evaluated. If it was, its memoized value is returned (lines 8-9). Otherwise, we need to evaluate this result, and this is where we make the recursive call (lines 11-12). Here before returning, we memoize the result in memo[n]. We do not need to memoize base cases, as they are already usually O(1) operations.
Practice Dynamic Programming Problems
Now give it a try yourself! Here’s some practice questions pulled from our interactive Dynamic Programming in Python course. Many of these problems are common in coding interviews to test your dynamic programming skills. Having a familiarity with these problems will make you a better candidate.
Check out of few of the following examples!
Knapsack Problem
Problem Statement:
Given a list of weights and a list of costs, find the optimal subset of things that form the highest cumulative price bounded by the capacity of the knapsack.
You should not change the signature of the given function; however, you may create a new function with a different signature and call it from the provided function.
Try to think of a simple solution to this problem. Once you have implemented that, add the memoization to account for more complex problems.
Sample Inputs:
weights = [1, 2, 4, 6]
prices = [4, 2, 4, 7]
capacity = 7
Solution:
def solveKnapsack(weights, prices, capacity, index, memo):
# base case of when we have run out of capacity or objects
if capacity <= 0 or index >= len(weights):
return 0
# check for solution in memo table
if (capacity, index) in memo:
return memo[(capacity, index)]
# if weight at index-th position is greater than capacity, skip this object
if weights[index] > capacity:
# store result in memo table
memo[(capacity, index)] = solveKnapsack(weights, prices, capacity, index + 1, memo)
return memo[(capacity, index)]
# recursive call, either we can include the index-th object or we cannot, we check both possibilities and return the most optimal one using max
memo[(capacity, index)] = max(prices[index]+solveKnapsack(weights, prices, capacity - weights[index], index+1, memo),
solveKnapsack(weights, prices, capacity, index + 1, memo))
return memo[(capacity, index)]
def knapsack(weights, prices, capacity):
# create a memo dictionary
memo = {}
return solveKnapsack(weights, prices, capacity, 0, memo)
print(knapsack([2,1,1,3], [2,8,1,10], 4))
-->
18
Solution Breakdown:
In this problem, it is a little hard to see overlapping problems, since they do not follow a specific pattern. But if you look closely, you will notice capacity and index tuple are oftentimes repeating. All of these sub-problems have the same answers. Look at the following visualization:
As we can see from the visualization, we can memoize based on a tuple of capacity and index. That is the only add-on in this code over the previous one with simple recursion. Before the recursive step, we check if the result is already available to us in the memo table. Similarly, after the evaluation of the result, we store it in the memo table again.
Coin-Change Problem
This is a version of the “Coin-Change Problem” commonly asked in coding interviews.
Problem Statement:
Given a list of currency bills, you are required to count the number of ways in which you can represent a certain amount. For example, if you have only two kinds of bills, $10 and $20, and you want to represent $30, there are only two ways:
3 bills of $10
1 bill of $20 and 1 bill of $10.
As you design the algorithm, take special care that you do not overcount. $30 can be represented with $20+$10 as well as $10+$20, but these are the same thing. Therefore, you should not count both cases.
A simple recursive solution will timeout for large inputs; thus, you should try to write a dynamic programming algorithm. Start with a recursive solution and build up to a dynamic solution.
Recursive Solution:
def countways_(bills, amount, index):
if amount == 0: # base case 1
return 1
if amount < 0 or index >= len(bills): # base case 2
return 0
# count the number of ways to make amount by including bills[index] and excluding bills[index]
return countways_(bills, amount - bills[index], index) + countways_(bills, amount, index+1)
def countways(bills, amount):
return countways_(bills, amount, 0)
print(countways([1,2,5], 5))
-->
4
Recursive Solution Breakdown:
Finding different combinations in a set of things is not difficult. In fact, one of the first problems we did in this course was finding different permutations of a string. The challenging bit was how to avoid overcounting due to the same permutations.
For example, $10 + $20 adds to $30, so does $20 + $10. In the context of permutations, both of these sequences would be distinct, but in the case of combinations, these are the same, meaning we must not count them twice. We achieve this by restricting each recursive call to use a subset of bills.
The key part of this solution is the sum of two recursive calls in line 7. To count to amount, some combinations will either include a specific bill given by bills[index] or they won’t. So, we can simply count both these possibilities. The first call to countways_ counts bills[index] as a part of the solution, whereas the second call skips over it.
Let’s see a simple visualization of this algorithm:
def countways(bills, amount):
if amount <= 0:
return 0
dp = [[1 for _ in range(len(bills))] for _ in range(amount + 1)]
for amt in range(1, amount+1):
for j in range(len(bills)):
bill = bills[j]
if amt - bill >= 0:
x = dp[amt - bill][j]
else:
x = 0
if j >= 1:
y = dp[amt][j-1]
else:
y = 0
dp[amt][j] = x + y
return dp[amount][len(bills) - 1]
print(countways([1,2,5], 5))
-->
4
Dynamic Solution Breakdown:
This implementation is based on the algorithm we discussed in solution one.
To make up an amount using n bills, we just need to count the ways that we can either make the amount using the n^th bill (lines 8-9) or without using it (lines 12-13).
The algorithm is easier to understand with the visualization given below:
For more dynamic programming problems, check out 6 Dynamic Programming problems for your next coding interview.
What to learn next
After completing our tutorial, you can hopefully see how powerful a tool this is for Python developers. Not only are these concepts tested in coding interviews but they’re also essential for creating efficient real world Python applications.
Now that you’ve taken your first steps, the best thing to do is study up on when to use top-down vs bottom-up and to keep practicing more problems of various types.
Educative’s course Dynamic Programming in Python: Optimizing Programs for Efficiency is a great place to get all that you need to continue your journey. Within you’ll find dozens of lessons, deep-dives and practice problems, all written by Python developers to help you get hands-on experience.
By the end, you’ll know how to identify a dynamic programming problem, learned when to use top-down or bottom-up, and have enough in-depth practice to wow any interviewer or coworker.
Wrapping up and resources
Congratulations on taking yet another step in perfecting your Python abilities. Today, we brought you through the what, why and how of dynamic programming and got some real interview question practice under your belt.
Moving from writing basic code to efficient code marks a great milestone in your learning. While it can be a steep learning curve, know that with each dynamic solution you create makes you that much more qualified and in-demand in our modern development space!
Continue reading about Python on Educative
- Level up your Python skills with these 6 challenges
- A Complete Guide to Web Development in Python
- 50 Python Interview Questions and Answers
Start a discussion
What is your favorite use of Dynamic Programming? Was this article helpful? Let us know in the comments below!
Top comments (0)