willcool4ever • 动态规划：硬币找零

硬币找零问题，我们在贪心算法那一节中讲过一次。我们今天来看一个新的硬币找零问题。假设我们有几种不同币值的硬币 v1，v2，……，vn（单位是元）。如果我们要支付 w 元，求最少需要多少个硬币。比如，我们有 3 种不同的硬币，1 元、3 元、5 元，我们要支付 9 元，最少需要 3 个硬币（3 个 3 元的硬币）。

思路分析：

非常简单的动态规划表，统计在上一次情况的基础上，加上一枚1或3或5金额硬币之后的情况。如果该行有等于money的情况，返回即可（说明加到本轮，已经可以满足）。
代码实现

// Example program
#include <iostream>
#include <vector>

using namespace std;

int minCoins(int money)
{

    if (money == 1 || money == 3 || money == 5)
        return 1;
    vector<<