目录

  1. 第二题（Leetcode原题）
    1. 题目描述
    2. 输入描述
    3. 输出描述
    4. 分析

第二题（Leetcode原题）

题目描述

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

输入描述

第一行为总金额n，第二行为所有硬币的面额。

输出描述

若存在可以凑成总金额所需的最少的硬币个数，则输出该数；否则输出为-1。

分析

  • 一开始想的是用贪心算法，但后来发现不可以，比如输入总金额为20、硬币面额为1、5、6时，若采用贪心算法：20=6*3+1*2，一共需要5枚硬币，而实际只需4枚硬币即可，即20=5*4。
  • 标准解法是动态规划算法：
    • 定义dp[i]为总金额为i时所需要的最少硬币数，dp[0]=0；
    • 状态转移方程：dp[i] = min(dp[i], dp[i-coin[j]] + 1)。+1是代表使用coin[j]一次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int getMinCoins(int n, const vector<int>& coin) {
    vector<int> dp(n + 1, n + 1);
    dp[0] = 0;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j < coin.size(); ++j) {
            if (coin[j] <= i)
                dp[i] = dp[i] < dp[i-coin[j]] + 1 ? dp[i] : dp[i-coin[j]] + 1;
        }
    }
    return dp[n] > n ? -1 : dp[n];
}

int main() {
    int n; // 总金额
    cin >> n;
    vector<int> coin; // 存储硬币面额
    while (cin.get() != '\n') {
        int value;
        cin >> value;
        coin.push_back(value);
    }
    cout << getMinCoins(n, coin) << endl;
}