332. Coin Change

Today, I solved coin chnage.

Description:

https://leetcode.com/problems/coin-change/description/

 

In this problem, we should find the fewest number of coins that make up that amount. 

Solution:

 

This is the brute force solution. 

 

Let's say coin is [1, 3, 4, 5], and amount = 7.

dp[0] is always "0" (because no need to coin to get to 0)

dp[1] = 1

dp[2] = 2

dp[3] = 1 -> one 3coin

dp[4] = 1 -> one 4coin

dp[5] = 1 -> one 5coin

dp[6] = 2 -> one 1coin + one 5coin

 

Now look at dp[7]:

 

dp[7]

case 1: 1 + dp[6] = 1 + 2 = 3

case 3: 1 + dp[4] = 1 + 1 = 2

case 4: 1 + dp[3] = 1 + 1 = 2

case 5: 1 + dp[2] = 1 + 2 = 3 

 

If the amount is 7, then we can see the minimum case is 2.