Part of course:
- Tiling problem
- First solution (recursion)
- How slow is our solution?
- Dynamic Programming solution (memoization)
- How fast is the dynamic programming solution?
- Technical definitions (theory)
- Next steps
Dynamic programming is a fancy name for storing intermediate results and re-using the stored result instead of re-computing them each time.
We'll first see an example of a dynamic programming problem. Technical definitions are introduced at the end of the tutorial.
Problem: You are given a grid of size n \times 2 and n tiles of size 2 \times 1. In how many different ways can you tile the grid such that the entire grid is covered and no tiles overlap. (The tiles look identical to each other. Two ways of tiling are different based on whether the tiles are placed horizontally or vertically).
Example: There are 3 possible ways of tiling a 3 \times 2 grid.
Tiling 1:Three vertical tiles__ __ __| | | ||__|__|__|Tiling 2:1 vertical tile, followed by 2 horizontal tiles__ _____| |_____||__|_____|Tiling 3:2 horizontal tiles, followed by 1 vertical tile_____ __|_____| ||_____|__|
In any tiling of the n \times 2 grid, the bottom-left square will either be covered with a vertical tile, or a horizontal tile.
Since the bottom left square can only be tiled in these two distinct ways, the number of ways to tile a n \times 2 grid is the sum of the number of ways to tile a (n-1) \times 2 grid and the number of ways to tile a (n-2) \times 2grid.
Hence, we can define a function f(n) = number of ways of tiling an n \times 2 grid = f(n-1) + f(n-2).
This gives us a recursive solution. So we need a few base cases. In this case, f(1) = 1 (number of ways of tiling a 1 \times 2 grid) and f(2) = 2 (number of ways of tiling a 2 \times 2 grid).
def tile(n):# base caseif n == 1: return 1if n == 2: return 2# recursive casereturn tile(n-1) + tile(n-2)
Now, let's see what happens when we call tile(7). This is how the recursion expands.
tile(7)/ \/ \/ \tile(6) tile(5)/ \ / \tile(5) tile(4) tile(4) tile(3)/ \ / \ / \ / \tile(4) tile(3) tile(3) tile(2) tile(3) tile(2) tile(2) tile(1). . . . .. . . . .
In total, tile(6) will be called once, tile(5) will be called 2 times, tile(4) is called 3 times, tile(3) is called 5 times, tile(2) is called 8 times ...
In general, the size of the above recursion tree is exponential in n. Our solution is really slow.
Notice that in the above solution, what we are calculation the same value repeatedly. For example, we calculate tile(3) 5 times. There's a simple fix to this, store the values when after calculating.
# solution with memoizationanswer = [None, None, None, ... (n times) ... ]def tile(n):if answer[n] is None: # answer is not stored (*)# calculate the answer ..................(*)# base caseif n == 1: result = 1if n == 2: result = 2# recursive caseresult = tile(n-1) + tile(n-2)answer[n] = result # store the answer .. (*)return answer[n] # return stored answer .... (*)
The important lines in the above code are marked with a (*).
The new recursion tree looks as follows:
tile(7)/ \/ \/ \tile(6) tile(5)/ \tile(5) tile(4)/ \tile(4) tile(3). .. .
This is because tile(5) called tile(4) + tile(3) exactly once. Once it is calculated, if it is called again, it doesn't do any calculations. Notice the large amounts of time savings here. The entire subtree below the tile(5) on the right is missing.
There's another way to implement the same solution, bottom-up.
# bottom-up implementationdef tile(n):answer = [None, None, None, ... (n times) ... ]# base caseanswer = 1answer = 2# recursive casefor i in 3 ... n:answer[i] = answer[i-1] + answer[i-2]return answer[n]
Note that although implementing the bottom-up solution is much simpler for this problem, in general, which solution is easier to implement (memoization vs bottom-up) depends on the specific problem.
Both the dynamic programming implementations are O(n), i.e. linear run-time. This might be slightly tougher to see in the memoization implementation, but notice that each node gets expanded only once. Hence, the total number of nodes is definitely smaller than 3n = O(n).
It is useful to be familiar with some technical definitions related to dynamic programming.
The two important properties a solution needs to have for it to be considered dynamic programming is
A dynamic programming solution consists of two main parts.
There are in general two ways of implementing dynamic programming solutions to problems. The first method is recursive with memoization, and the second method is bottom-up and iterative.
For trivia about why Dynamic Programming is named so, a video and other information, check out the posts in this discussion.
The best way to get better at dynamic programming is to solve different kinds of dynamic programming problems. This is what we will be doing in the upcoming tutorials.