Dynamic Programming Primer
We’re about to start our final stretch of Haskell/Rust LeetCode comparisons (for now). In this group, we’ll do a quick study of some dynamic programming problems, which are a common cause of headache on programming interviews. We’ll do a couple single-dimension problems, and then show DP in multiple dimensions. Haskell has a couple interesting quirks to work out with dynamic programming, so we’ll try to understand that by comparison to Rust.
Dynamic programming is one of a few different algorithms you’ll learn about in Module 3 of Solve.hs, our Haskell problem solving course. Check it out today!
The Problems
Today’s problem is called House Robber. Normally we wouldn’t want to encourage crime, but when people have such a convoluted security set up as this problem suggests, perhaps they can’t complain.
The idea is that we receive a list of integers, representing the value that we can gain from “robbing” each house on a street. The security system is set up so that the police will be alerted if and only if two adjacent houses are robbed. So we could rob every other house, and no police will come.
We are trying to determine the maximum value we can get from robbing these houses without setting off the alarm (by robbing adjacent houses).
Dynamic Programming Introduction
As mentioned in the introduction, we’ll solve this problem using dynamic programming. This term can mean a couple different things, but by and large the idea is that we use answers on smaller portions of the input (going down as far as base cases) to build up to the final answer on the full input.
This can be done from the top down, generally by means of recursion. If we do this, we’ll often want to “cache” answers (Memoization) to certain parts of the problem so we don’t do redundant calculations.
We can also build answers from the bottom up (tabulation). This often takes the form of creating an array and storing answers to smaller queries in this array. Then we loop from the start of this array to the end, which should give us our answer. Our solutions in this series will largely rest on this tabulation idea. However, as we’ll see, we don’t always need an array of all prior answers to do this!
The key in dynamic programming is to define, whether for an array index or a recursive call, exactly what a “partial” solution means. This will help us use partial solutions to build our complete solution.
The Algorithm
Now let’s figure out how we’ll use dynamic programming for our house robbing problem. The broad idea is that we could define two arrays, the “robbed” array and the “unrobbed” array. Each of these should be equal in size to the number of houses on the street. Let’s carefully define what each array means.
Index i of the “robbed” array should reflect the maximum value we can get from the houses [0..i] such that we have “robbed” house i. Then the “unrobbed” array, at index i, contains the maximum total value we can get from the houses [0..i] such that we have not robbed house i.
When it comes to populating these arrays we need to think first about the base cases. Then we need to consider how to build a new case from existing cases we have. With a recursive solution we have the same pattern: base case and recursive case.
The first two indices for each can be trivially calculated; they are our base cases:
robbed[0] = input[0] // Rob house 0
robbed[1] = input[1] // Rob house 1
unrobbed[0] = 0 // Can’t rob any houses
unrobbed[1] = input[0] // Rob house 0Now we need to build a generic case i, assuming that we have already calculated all the values from 0 to i - 1. To calculate robbed[i], we assume we are robbing house i, thus we add input[i]. If we are robbing house i we must not have robbed house i - 1, so we add this value to unrobbed[i - 1].
To calculate unrobbed[i], we have the option of whether or not we robbed house i - 1. It may be advantageous to skip two houses in a row! Consider an example like [100, 1, 1, 100]. So we take the maximum of unrobbed[i - 1] and robbed[i - 1].
This gives us our general case, and so at the end we simply select the maximum of robbed[n - 1] and unrobbed[n - 1].
We’ve been speaking in terms of arrays, but we can observe that we only need the i - 1 value from each array to construct the i values. This means we don’t actually have to store a complete array, which would take O(n) memory. Instead we can store the last “robbed” number and the last “unrobbed” number. This makes our solution O(1) memory.
Haskell Solution
Now let’s write some code, starting with Haskell! LeetCode guarantees that our input is non-empty, but we still need to handle the size-1 case specially:
robHouse :: V.Vector Int -> Int
robHouse nums = if n == 1 then nums V.! 0
else ...
where
n = V.length nums
...Now let’s write a recursive loop function that will take our prior two values (robbed and unrobbed) as well as the index. These are the “stateful” values of our loop. We’ll use these to either return the final value, or make a recursive call with new “robbed” and “unrobbed” values.
robHouse :: V.Vector Int -> Int
robHouse nums = if n == 1 then nums V.! 0
else ...
where
n = V.length nums
loop :: (Int, Int) -> Int -> Int
loop (lastRobbed, lastUnrobbed) i = ...For the “final” case, we see if we have reached the end of our array (i = n), in which case we return the max of the two values:
robHouse :: V.Vector Int -> Int
robHouse nums = if n == 1 then nums V.! 0
else ...
where
n = V.length nums
loop :: (Int, Int) -> Int -> Int
loop (lastRobbed, lastUnrobbed) i = if i == n then max lastRobbed lastUnrobbed
else ...Now we fill in our recursive case, using the logic discussed in our algorithm:
robHouse :: V.Vector Int -> Int
robHouse nums = if n == 1 then nums V.! 0
else ...
where
n = V.length nums
loop :: (Int, Int) -> Int -> Int
loop (lastRobbed, lastUnrobbed) i = if i == n then max lastRobbed lastUnrobbed
else
let newRobbed = nums V.! i + lastUnrobbed
newUnrobbed = max lastRobbed lastUnrobbed
in loop (newRobbed, newUnrobbed) (i + 1)Finally, we make the initial call to loop to get our answer! This completes our Haskell solution:
robHouse :: V.Vector Int -> Int
robHouse nums = if n == 1 then nums V.! 0
else loop (nums V.! 1, nums V.! 0) 2
where
n = V.length nums
loop :: (Int, Int) -> Int -> Int
loop (lastRobbed, lastUnrobbed) i = if i == n then max lastRobbed lastUnrobbed
else
let newRobbed = nums V.! i + lastUnrobbed
newUnrobbed = max lastRobbed lastUnrobbed
in loop (newRobbed, newUnrobbed) (i + 1)Even when tabulating from the ground up in Haskell, we can still use recursion!
Rust Solution
Our Rust solution is similar, just using a loop instead of a recursive function. We start by handling our edge case and coming up with the initial values for “last robbed” and “last unrobbed”.
pub fn rob(nums: Vec<i32>) -> i32 {
let n = nums.len();
if n == 1 {
return nums[0];
}
let mut lastRobbed = nums[1];
let mut lastUnrobbed = nums[0];
...
}Now we just apply our algorithmic logic in a loop from 2 to n, resetting lastRobbed and lastUnrobbed each time.
pub fn rob(nums: Vec<i32>) -> i32 {
let n = nums.len();
if n == 1 {
return nums[0];
}
let mut lastRobbed = nums[1];
let mut lastUnrobbed = nums[0];
for i in 2..n {
let newRobbed = nums[i] + lastUnrobbed;
let newUnrobbed = std::cmp::max(lastUnrobbed, lastRobbed);
lastRobbed = newRobbed;
lastUnrobbed = newUnrobbed;
}
return std::cmp::max(lastRobbed, lastUnrobbed);
}And now we’re done with Rust!
Conclusion
Next week we’ll do a problem that actually requires us to store a full array of prior solutions. To learn the different stages in building up an understanding of dynamic programming, you should take our problem solving course, Solve.hs. Module 3 focuses on algorithms, including dynamic programming!