Dynamic Programming 1D Coin Change in Swift

DP is one of the hardest parts of coding interview. The actual code is very short. But defining the small problem and deciding how to reuse previous value is hard.

In this post I’ll introduce a famous DP problem called Coin Change.

You are given coin denominations and a target amount. You can use each coin as many times as you want.

Input

coins: [1, 4, 6]

amount: 9

Output

Return the minimum number of coins needed to make the amount 9

Let’s solve it

Step 1. Current coin is $1

First, we fill the DP array with Int.max and set dp[0] to 0. Using the $1 coin, we can make $1 with one coin, so dp[1] becomes 1

To make $2 with the $1 coin, we use the result for $1 and add one more coin. Therefore, dp[2] = dp[1] + 1 = 2

To make $3, we reuse the result for $2 and add one $1 coin. Therefore, dp[3] becomes 3

We use the same rule for $4. Since dp[3] is 3, adding one more $1 coin makes dp[4] = 4

To make $5, we start from the result for $4 and add one more coin. Therefore, dp[5] becomes 5

To make $6 with only the $1 coin, we need six coins. We calculate it using dp[5] + 1

For $7, we reuse dp[6] and add one more $1 coin. Therefore, dp[7] becomes 7

For $8, the previous result is dp[7] = 7. Adding one more $1 coin makes dp[8] = 8

For $9, using only the $1 coin requires nine coins. This completes the first pass for coin 1, but it is not the final answer yet.

Step 2. Current coin is $4

Now we process the $4 coin, starting from amount $4. We compare the previous value 4 with dp[0] + 1, so dp[4] becomes 1

To make $5, we add one $4 coin to the best result for $1. Since dp[1] + 1 = 2 is better than 5, dp[5] becomes 2

To make $6, we add one $4 coin to the best result for $2. Therefore, dp[6] is updated from 6 to 3

To make $7, we use the best result for $3 and add one $4 coin. This changes dp[7] from 7 to 4.

To make $8, we use the updated result for $4 and add another $4 coin. Two $4 coins are better than eight $1, so dp[8] becomes 2.

To make $9, we use the updated result for $5 and add one $4 coin. The best combination is $4 + $4 + $1, so dp[9] becomes 3.

Step 3. Current coin is $6

Finally, we process the $6 coin, starting from amount $6. One $6 coin is better than the previous 3 coins result. so dp[6] becomes 1.

To make $7, we add one $6 coin to the best result for $1. Since dp[1] + 1 = 2 is better than the previous value 4, dp[7] becomes 2.

To make $8, using a $6 coin would require 3 coins: $6 + $1 + $1. The previous result $4 + $4 uses only 2 coins, so dp[8] stays 2.

To make $9, using a $6 coin would require 4 coins. The previous combination $4 + $4 + $1 needs only 3 coins, so dp[9] stays 3.

After checking every coin, dp[9] is 3. Therefore, the minimum number of coins needed to make $9 is 3.

Full code in Swift

import Foundation
func coinChange(_ coins: [Int], _ amount: Int) -> Int {
    var dp = Array(repeating: Int.max, count: amount + 1)
    dp[0] = 0
    
    for coin in coins {
        for current in coin...amount {
            dp[current] = min(
                dp[current],
                dp[current - coin] + 1
            )
        }
        
    }
    let result = dp[amount] != Int.max ? dp[amount] : -1
    print("result: \(result)")
    return result
}
coinChange([1, 4, 6], 9)

Conclusion

With less than 15 lines of code, we solved the Coin Changes problem.

The code is short, but the important part is defining what each DP value means and how to reuse previous results.

When solving a 1D DP problems, ask your self these five questions:

• What exactly does dp[i] mean?
• What choices do I have at the current position?
• Which previous result does each choice use?
• What is the starting value?
• Where is the final answer in the DP array?

We can use the same DP thinking for other 1D DP problems:

• LeetCode 70: Climbing Stairs
• LeetCode 746: Min Cost Climbing Stairs
• LeetCode 198: House Robber
• LeetCode 2140: Brainpower
• LeetCode 322: Coin Change
• LeetCode 300: LIS

Next post, I’ll write about 2D DP problem.