Dynamic programming sounds fancier than it is. At its core, it is an optimization method. Let’s take a look at a problem from the foundations of the backtracking algorithms, we can brute force a working solution, then optimize it with dynamic programming.
Starting with the house robber problem.
A security system for a row of houses will automatically call the police if two houses in a row are robbed.Given an array of houses N with different robbery values, what is the maximum value we can rob without alerting the police?Input: nums = [1,2,3,1]
Output: 4
As a robber, we decide to steal from a house or not as we pass by. If we steal from one house, then we cannot steal from the next one. The same pattern occurs for the next house over. At every point, we decide on two things, either we steal from the house or we ignore it. If we design this like a backtracking problem, we get the following algorithm.
- We steal from the current house, then we skip the next house and start the decision process again.
- We don’t steal from the current house, then we steal from the next houses and start the decision process again.
- Take a maximum of 1 or 2.
Coding it out, we have the following recursive method.
Reducing the code to a formula, we get T(n) = max(T(n-1), h(n) + T(n-2)). In prose, the maximum value of robbing houses is the best return from skipping the current house and robbing the next house T(n-1); or Robbing the current house h(n) and robbing the next house over T(n-2).
Note: We use n-1 to indicate the next house because the array gets smaller as we pass each house.
I’m going to skip over the math here, but suffice it to say that evaluating it provides a time complexity of O(2^n) (cheat sheet). Whilst the solution makes sense, it is very slow! The algorithm we created spends a lot of time checking branches that have already been calculated. Expanding the formula:
# Removed h(n) to make it easier to read
T(n) = max(T(n-1), T(n-2))
T(n-1) = max(T(n-2), T(n-3))
T(n-2) = max(T(n-3), T(n-4))# Switched to plus signs here, since its easier to read than max(max(max….
T(n-1) = [T(n-2), T(n-3)]
T(n-2) = [T(n-3), T(n-4)]
T(n) = [T(n-2) ,T(n-3)] + [T(n-3) ,T(n-4)]# Expanding some more…
T(n) = [[T(n-3) ,T(n-4)] , T(n-3)] + [T(n-3) , T(n-4)]
It looks like we are re-calculating the same T(n-3) result numerous times! This is where the inefficiency occurs! The gist of dynamic programming is to identify these repeated subproblems and prevent repeated work.
We can optimize our solution by keeping track of each result calculated and return a stored value. Adding a dictionary helps us do this.
In the previous code snippet, we added a dictionary mem to store the inputs into the rob_houses function. We keep track of the inputs to the method and return a value from memory instead of re-calculating it. Though we can optimize even further by removing recursion altogether!
Calculating the maximum criminal gains requires referencing the previous values. Recursion doesn’t help us since most of the recursive method calls return from memory. We can replace the recursive problem with an array.
To do this, we reframe the algorithm to calculate the max value stolen at the current house, using the 2 previously calculated max values as inputs. It is the same T(n) = max(T(n-1), h(n) + T(n-2)) formula, but with modifications to how we calculate values since we no longer use recursion.
Pretty neat right? Well, we can go further and just skip the array here as well. At every house, we only need the maximum value so far, and the previous maximum to calculate our answer. If we take a step back and think about it. The previous implementation only looked at the previous 2 array values, with some funky variable manipulation we can make do with 2 variables.
Using a max_so_far to keep track of our optimal criminal gains and prev_max to keep track of the max value of the house 2 spaces back. This implementation follows the classic Kadane’s algorithm template. We call the house robber problem a 1 dimensional (1D) dynamic programming problem because it uses a 1D array to store the answers to sub-problems. Kadane’s algorithm is a well-known template for 1D dynamic programming problems.
Summary
What we did today was brute force a solution with backtracking, then attempt to discover repeating patterns. Once we found a pattern, iteratively reduced the repeated work until we arrive at a dynamic programming solution.
I hope this has helped demystify the thinking process to arrive at a typical looking DP answer. Most DP interview problems fall under common patterns. The difficult part is being able to correctly identify the sub-problems. Iterating the question through back-tracking and deriving the recurrence relationship is a good way to discover the repeating sub-problem.
For more patterns, feel free to check out the common patterns and 2D dynamic programming here https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns.
