找钱(Coin change)

  1. /// Coin change via Dynamic Programming
  3. /// coin_change(coins, amount) returns the fewest number of coins that need to make up that amount.
  4. /// If that amount of money cannot be made up by any combination of the coins, return `None`.
  5. ///
  6. /// Arguments:
  7. ///     * `coins` - coins of different denominations
  8. ///     * `amount` - a total amount of money be made up.
  9. /// Complexity
  10. ///     - time complexity: O(amount * coins.length),
  11. ///     - space complexity: O(amount),
  12. pub fn coin_change(coins: &[usize], amount: usize) -> Option<usize> {
  13.     let mut dp = vec![std::usize::MAX; amount + 1];
  14.     dp[0] = 0;
  16.     // Assume dp[i] is the fewest number of coins making up amount i,
  17.     // then for every coin in coins, dp[i] = min(dp[i - coin] + 1).
  18.     for i in 0..=amount {
  19.         for j in 0..coins.len() {
  20.             if i >= coins[j] && dp[i - coins[j]] != std::usize::MAX {
  21.                 dp[i] = dp[i].min(dp[i - coins[j]] + 1);
  22.             }
  23.         }
  24.     }
  26.     match dp[amount] {
  27.         std::usize::MAX => None,
  28.         _ => Some(dp[amount]),
  29.     }
  30. }
  32. #[cfg(test)]
  33. mod tests {
  34.     use super::*;
  36.     #[test]
  37.     fn basic() {
  38.         // 11 = 5 * 2 + 1 * 1
  39.         let coins = vec![1, 2, 5];
  40.         assert_eq!(Some(3), coin_change(&coins, 11));
  42.         // 119 = 11 * 10 + 7 * 1 + 2 * 1
  43.         let coins = vec![2, 3, 5, 7, 11];
  44.         assert_eq!(Some(12), coin_change(&coins, 119));
  45.     }
  47.     #[test]
  48.     fn coins_empty() {
  49.         let coins = vec![];
  50.         assert_eq!(None, coin_change(&coins, 1));
  51.     }
  53.     #[test]
  54.     fn amount_zero() {
  55.         let coins = vec![1, 2, 3];
  56.         assert_eq!(Some(0), coin_change(&coins, 0));
  57.     }
  59.     #[test]
  60.     fn fail_change() {
  61.         // 3 can't be change by 2.
  62.         let coins = vec![2];
  63.         assert_eq!(None, coin_change(&coins, 3));
  64.         let coins = vec![10, 20, 50, 100];
  65.         assert_eq!(None, coin_change(&coins, 5));
  66.     }
  67. }