322. Coin Change

Description of the Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4.

Solution

Tags: Permutation and Combination Dynamic Programming

Explanation

Intuitively, if the amount of coins is "divisible", the fewest possible number of coins is 1. Thus, if the amount is equals to one of the denominations, then it should return 1.

For any amount of coins, we can try every possible denominator to find the minimum number of coins. See the following equations:

\[ \text{min_coins}(n) = \begin{cases} 0 & \text{if n is 0} \\ 1 & \text{if n is one of the denominators} \\ +\infty & \text{if n is negative} \\ \min_{c \ \in \ Denominators} \{ 1 + \text{min_coins}(n-c) \} & \text{otherwise} \end{cases} \]

However, recursive approach may be very slow. It is more preferable to use Dynamic Programming approach because each solution is depended on smaller sub-solution.

Code

impl Solution {
    pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
        let amount = amount as usize;
        let mut dp = vec![None ; amount + 1];
        dp[0] = Some(0);
        for i in 1..=amount{
            for &chosen_coin in coins.iter() {
                if i >= chosen_coin as usize {
                    let mx = dp[i];
                    let my = dp[i-chosen_coin as usize];
                    dp[i] = match (mx,my){
                        (None,None)=>None,
                        (Some(x),None)=>Some(x),
                        (None,Some(y))=>Some(y+1),
                        (Some(x),Some(y))=>Some(x.min(y+1)),
                    };
                }

            }
        }

        if let Some(sol) = dp[amount] { sol } else { -1 }
    }

}

Complexity

Time complexity:

\(O(n k)\)
- \(n\) is amount of money and \(k\) is number of coins of different denominations

Auxiliary Space:

\( \Theta(n) \)

Leetbook