2020/3/15

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例

示例：

示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例 2:
输入: coins = [2], amount = 3
输出: -1

相关标签

动态规划

解题思路

• 算法：
  自底向上的动态规划，F(n) 表示金额 n 需要的最少硬币组成
  F(i) 最小硬币数量
  F(0) 0 //金额为0不能由硬币组成
  F(1) 1 //F(1)=min(F(1-1),F(1-2),F(1-5))+1=1
  F(2) 1 //F(2)=min(F(2-1),F(2-2),F(2-5))+1=1
  F(3) 2 //F(3)=min(F(3-1),F(3-2),F(3-5))+1=2
  F(4) 2 //F(4)=min(F(4-1),F(4-2),F(4-5))+1=2
  ......
  F(11) 3 //F(11)=min(F(11-1),F(11-2),F(11-5))+1=3

• 复杂度分析：
  时间复杂度：O(N)
  空间复杂度：O(N)

源代码

use std::collections::HashMap;

impl Solution {
    pub fn coin_change(mut coins: Vec<i32>, amount: i32) -> i32 {
        let mut store: HashMap<i32, i32> = HashMap::new();
        coins.sort();
        store.insert(0, 0);
        for coin in &coins {
            store.insert(*coin, 1);
        }
        
        for _amount in coins[0]*2..amount+1 {
            if let Some(coin_num) = store.get(&_amount) {
                continue;
            }

            if _amount % *coins.last().unwrap() == 0 {
                store.insert(_amount, _amount / *coins.last().unwrap());
                continue;
            }

            let mut coin_num = std::i32::MAX;
            let mut t = 0;
            for coin in coins.iter().rev() {                
                if let Some(_coin_num) = store.get(&(_amount-*coin)) {
                    if coin_num > *_coin_num + 1 {
                        coin_num = *_coin_num + 1;
                        t += 1;              
                    }                                            
                }
                else { continue; }
            }

            if coin_num != std::i32::MAX { store.insert(_amount, coin_num); }
        }
        
        *store.get(&amount).unwrap_or(&-1)
    }
}

执行用时 : 148 ms, 在所有 Rust 提交中击败了28.57%的用户
内存消耗 : 2.3 MB, 在所有 Rust 提交中击败了100.00%的用户

总结

本题采用贪心 + 剪枝的方法似乎更快，有空补上。