Making Change: Array-Based DP

Written By James Bowen

Today we’ll continue the study of Dynamic Programming we started last week. Last week’s problem let us use a very compact memory footprint, only remember a couple prior values. This week, we’ll study a very canonical DP problem that really forces us to store a longer array of prior values to help us populate the new solutions.

For an in-depth study of Dynamic Programming in Haskell and many other problem solving techniques, take a look at our Solve.hs course today! Module 3 focuses on algorithms, and introduces several steps leading up to understanding DP.

The Problem

Our problem today is Coin Change, and it’s relatively straightforward. We are given a list of coin values, and an amount to make change for. We want to find the smallest number of coins we can use to provide the given amount (or -1 if the amount cannot be made from the coins we have).

So for example, if we have coins [1,2,5], and we are trying to make 11 cents of change, the answer is 3 coins, because we take 2 5 coins and 1 1 coin.

If we have the coins [2,10,15] and the amount is 13, we should return -1, since there is no way to make 13 cents from these coins.

The Algorithm

Let us first observe that a greedy algorithm does not work here! We can’t simply take the largest coin under the remaining amount and then recurse. If we have coins like [1, 20, 25] and the amount is 40, we can do this with 2 coins (both 20), but taking a 25 coin to start is suboptimal.

The way we will do this is to build a DP array so that index i represents the fewest coins necessary to produce the amount i. All values are initially -1, to indicate that we might not be able to satisfy the number. However, we can set the index 0 as 0, since no coins are needed to give 0 cents.

So we have our base case, but how do we fill in index i, assuming we’ve filled in everything up to i - 1? The answer is that we will consider each coin we can use, and look back in the array based on its value. So if 5 is one of our coins, we’ll consider just adding 1 to the value at index i - 5. We’ll take the minimum value based on looking at all the different coin options, being careful to observe edge cases where no values are possible.

Unlike the last problem, this does require us to keep a larger array of values. We’re not just reaching back for the prior value in our array, we’re considering values that are much further back. Plus the amount of look-back we need is dynamic depending on the problem inputs.

We’ll write a solution where the array has size equal to the given amount (plus 1). It would be possible to instead use a structure whose size simply covers the range of possible coin values, but this becomes considerably more difficult.

Rust Solution

We’ll start with the Rust solution, since modifying arrays is more natural in Rust. What is unnatural in Rust is mixing integer types. Everything has to be usize if we’re going to index into arrays with it, so let’s start by converting the amount and the coins into usize:

```rust
pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
    let n = amount as usize;
    let cs: Vec<usize> = coins.into_iter().map(|x| x as usize).collect();
    ...
}

Now we’ll initialize our dp array. It should have a size equal to the amount plus 1 (we want indices 0 and amount to be valid). Most cells should initially be -1, but we’ll make the 0 index equal to 0 as our base case (no coins to make 0 cents of change). We’ll also return the final value from this array as our answer.

pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
    let n = amount as usize;
    let cs: Vec<usize> = coins.into_iter().map(|x| x as usize).collect();
    let mut dp = Vec::with_capacity(n + 1);
    dp.resize(n + 1, -1);
    dp[0] = 0;
    ...
    return dp[n];
}

Let’s set up our loops. We go through all the indices from 1 to amount, and loop through all the coins for each index.

pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
    let n = amount as usize;
    let cs: Vec<usize> = coins.into_iter().map(|x| x as usize).collect();
    let mut dp = Vec::with_capacity(n + 1);
    dp.resize(n + 1, -1);
    dp[0] = 0;
    for i in 1..=n {
        for coin in &cs {
            ...
        }
    }
    return dp[n];
}

Now let’s apply some rules for dealing with each coin. First, if the coin is larger than the index, we do nothing, since we can’t use it for this amount. Otherwise, we try to use it. We get a “previous” value for this coin, meaning we look at our dp table going back the number of spaces corresponding to the coin’s value.

pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
    ...
    for i in 1..=n {
        for coin in &cs {
            if *coin <= i {
                let prev = dp[i - coin];
                ...
            }
        }
    }
    return dp[n];
}

If the prior value is -1, we can ignore it. This means we can’t actually use this coin to form the value at this index. Otherwise, we look at the current value in the dp table for this index. We may have a value here from previous coins already. If this value is not -1, and it is larger than the value we get from using this new coin, we replace the value in the dp table:

pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
    let n = amount as usize;
    let cs: Vec<usize> = coins.into_iter().map(|x| x as usize).collect();
    let mut dp = Vec::with_capacity(n + 1);
    dp.resize(n + 1, -1);
    dp[0] = 0;
    for i in 1..=n {
        for coin in &cs {
            if *coin <= i {
                let prev = dp[i - coin];
                if prev != -1 && (dp[i] == -1 || prev + 1 < dp[i]) {
                    dp[i] = prev + 1;
                }
            }
        }
    }
    return dp[n];
}

And this completes our solution!

Haskell Solution

In Haskell, immutability makes DP with arrays a bit more challenging. We could use mutable arrays, but these are a little tricky (you can learn about them in Solve.hs).

Instead we’ll learn on the IntMap type, which is just like Data.Map but always uses Int for keys. This structure is “mutable” in the same way as other map-like structures in Haskell. We’ll write a core loop that takes this map as its stateful input, as well as the index:

import qualified Data.IntMap.Lazy as IM

coinChange :: [Int] -> Int -> Int
coinChange coins amount = ...
  where
    loop :: IM.IntMap Int -> Int -> Int
    loop dp i = ...

A notable difference with how we’ll use our map is that we don’t have entries for invalid indices. These will be absent, and we’ll use fromMaybe with our map to consider that they might not exist. As a first example of this, let’s do the base case for our loop. Once the index i exceeds our amount, we’ll return the value in our map at amount, or -1 if it doesn’t exist:

coinChange :: [Int] -> Int -> Int
coinChange coins amount = ...
  where
    loop :: IM.IntMap Int -> Int -> Int
    loop dp i = if i > amount then fromMaybe (-1) (IM.lookup amount dp)
      else ...

Now we need to loop through the coins while updating our IntMap. Hopefully you can guess what’s coming. We need to define a function that ends with a -> b -> b, where a is the new coin we’re processing and b is the IntMap. Then we can loop through the coins with foldr. This function will also take our current index, which will be constant across the loop of coins:

coinChange :: [Int] -> Int -> Int
coinChange coins amount = ...
  where
    coinLoop :: Int -> Int -> IM.IntMap Int -> IM.IntMap Int
    coinLoop i coin dp = ...

    loop :: IM.IntMap Int -> Int -> Int
    loop dp i = if i > amount then fromMaybe (-1) (IM.lookup amount dp)
      else ...

We consider the “previous” value, which we call -1 if it doesn’t exist. We also consider the “current” value for index i, but we use maxBound if it doesn’t exist. This is because we want to insert a new number if it’s smaller, and maxBound will always be larger:

coinChange :: [Int] -> Int -> Int
coinChange coins amount = ...
  where
    coinLoop :: Int -> Int -> IM.IntMap Int -> IM.IntMap Int
    coinLoop i coin dp =
      let prev = fromMaybe (-1) (IM.lookup (i - coin) dp)
          current = fromMaybe maxBound (IM.lookup i dp)
      in  ...

If the prior value doesn’t exist, or if the existing value is smaller than using the previous value (plus 1), then we keep dp the same. Otherwise we insert the new value at this index:

coinChange :: [Int] -> Int -> Int
coinChange coins amount = ...
  where
    coinLoop :: Int -> Int -> IM.IntMap Int -> IM.IntMap Int
    coinLoop i coin dp =
      let prev = fromMaybe (-1) (IM.lookup (i - coin) dp)
          current = fromMaybe maxBound (IM.lookup i dp)
      in  if prev == (-1) || current < prev + 1 then dp
            else IM.insert i (prev + 1) dp

    loop :: IM.IntMap Int -> Int -> Int
    loop dp i = if i > amount then fromMaybe (-1) (IM.lookup amount dp)
      else ...

Now to complete our function, we just have to invoke these two loops. The primary loop we invoke with a base map assigning 0 to 0. The secondary loop relies on foldr and looping over the coins. We use this result in our recursive call:

coinChange :: [Int] -> Int -> Int
coinChange coins amount = loop (IM.singleton 0 0) 1
  where
    coinLoop :: Int -> Int -> IM.IntMap Int -> IM.IntMap Int
    coinLoop i coin dp =
      let prev = fromMaybe (-1) (IM.lookup (i - coin) dp)
          current = fromMaybe maxBound (IM.lookup i dp)
      in  if prev == (-1) || current < prev + 1 then dp
            else IM.insert i (prev + 1) dp

    loop :: IM.IntMap Int -> Int -> Int
    loop dp i = if i > amount then fromMaybe (-1) (IM.lookup amount dp)
      else loop (foldr (coinLoop i) dp coins) (i + 1)

And now we’re done!

Conclusion

Our first two problems have been simple, 1-dimensional DP problems. But DP really shines as a technique when applied across multiple dimensions. In the next two weeks we’ll consider some of these multi-dimensional DP problems.

For more practice with DP and other algorithms, sign up for Solve.hs, our Haskell problem solving course! The course has hundreds of practice problems so you can hone your Haskell skills!

James Bowen
Next

Dynamic Programming Primer