假设现在有面值为1元，3元，5元的硬币若干枚，如何用最少硬币数凑够需要的金额？现输入一个表示需要的金额，要求输出一个整数表示最少的硬币数。用c＋＋代码做出来

可以使用动态规划来解决这个问题。

具体来说，我们可以维护一个一维数组 dp，其中 dp[i] 表示凑够金额 i 所需的最少硬币数。

初始化时，dp[0]=0，因为凑够金额 0 不需要任何硬币。

接下来，我们从小到大枚举需要凑够的金额 j，对于每个 j，我们枚举每种面值的硬币，假设当前枚举到面值为 v 的硬币，那么如果 j>=v，说明我们可以将硬币 v 加入方案中。此时，凑够金额 j 所需的最少硬币数就等于 dp[j-v]+1 和 dp[j] 中较小的那个。

最终，dp[amount] 就是凑够金额 amount 所需的最少硬币数。

以下是用 C++ 实现的代码：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount+1, INT_MAX);
    dp[0] = 0;
    for (int j = 1; j <= amount; j++) {
        for (int i = 0; i < coins.size(); i++) {
            if (j >= coins[i] && dp[j-coins[i]] != INT_MAX) {
                dp[j] = min(dp[j], dp[j-coins[i]] + 1);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1, 3, 5};
    int amount = 11;
    cout << coinChange(coins, amount) << endl; // 输出 3
    return 0;
}