选硬币该用动态规划

选硬币：
现有面值分别为1角1分，5分，1分的硬币，请给出找1角5分钱的最佳方案。

#include <iostream>
#include <vector>std::vector<int> findChange(int amount) {std::vector<int> coins = {11, 5, 1}; // 按面值从大到小排序的硬币面值std::vector<int> result(coins.size(), 0); // 用于存储每种硬币的数量for (int i = 0; i < coins.size(); i++) {int numCoins = amount / coins[i]; // 计算当前硬币面值的数量result[i] = numCoins; // 存储数量amount -= numCoins * coins[i]; // 更新剩余金额}return result;
}int main() {int amount = 15; // 需要找零的金额，单位为分std::vector<int> change = findChange(amount);std::cout << "找零方案为：" << std::endl;std::cout << "1角1分硬币数量：" << change[0] << std::endl;std::cout << "5分硬币数量：" << change[1] << std::endl;std::cout << "1分硬币数量：" << change[2] << std::endl;return 0;
}

一开始我想的很简单，以为是简单的求整除数。
但要是你仔细一想，这肯定是不对的，不是所有问题都能用贪心。
在求最优的过程中，贪心和动态规划一直是一对冤家，到底选择哪个，难道了很多英雄好汉，所以最好的方式就是具体问题具体分析，只有结合实际情况才能选出最适合问题的算法。
我们都知道贪心的局限性，只能求出其中一个解的，但是不是最优需要考量。
让我们来看一下用上面贪心求出来的解：

但这肯定不是最优解，我们在找零的时候遵循的规则是用最少的钱张数交给别人，这样才方便。
所以最佳找零方案为：
1角1分硬币数量：0
5分硬币数量：3
1分硬币数量：0
让我们来看看用动态规划写出来的代码：

#include <iostream>
using namespace std;const int N = 10005;
const int INF = 0x3f3f3f3f; 
int f[N], a[N];int main() {int n, w;cin >> n >> w;for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 1; i <= w; i++) {f[i] = INF;}for (int i = 0; i < n; i++) {for (int j = a[i]; j <= w; j++) {f[j] = min(f[j], f[j - a[i]] + 1);}}if (f[w] == INF) {cout << -1; } else {cout << f[w];}return 0;
}

结果和我们预期的完全一样

总结

选硬币在动态规划中是一种叫状态表示的题型，通常用一维/二维的数组组成状态转移方程，通过更新数组来达到获取最优解的目标