硬币找零
有三种硬币，面值分别是2元、5元、7元，每种硬币都有足够多。买一个物品需要27元，如何用最少的硬币组合正好付清？
要让硬币最少，应该尽量用面值大的硬币，也就是贪心算法的结果为7 + 7 + 7 + 5 = 26，呃……
那么需要改变一下策略，尽量用面值大的硬币，最后如果可以用一种硬币付清就行。7 + 7 + 7 + 2 + 2 + 2 = 27，一共6枚硬币，应该对了吧……
但是正确答案是7 + 5 + 5 + 5 + 5 = 27，一共5枚硬币。
状态在动态规划中的作用属于定海神针，确定状态需要两个意识：最后一步和子问题。
虽然目前不知道最优策略是什么，但是最优策略肯定是k枚硬币面值加起来是27，所以一定存在最后一枚硬币。除了这枚硬币，前面硬币的面值加起来是。因为是最优策略，所以拼出的硬币数一定要最少。
因此问题就变成了最少用多少枚硬币可以拼出。这样就将原问题转化成了一个子问题，而且规模更小。
假设状态F(x)表示拼出x元的所需的最少硬币数，最后那枚硬币只可能是2元、5元或7元：
-
如果是2元，则这个候选方案的硬币数为 F(27-2) + 1（加上最后一枚2元硬币）。
-
如果是5元，则这个候选方案的硬币数为 F(27-5) + 1（加上最后一枚5元硬币）。
-
如果是7元，则这个候选方案的硬币数为 F(27-7) + 1（加上最后一枚7元硬币）。
由此可得到递归公式：
硬币找零（递归）
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
static int min_int(int a, int b) {
return a < b ? a : b;
}
int get_min_coins_recursive(int *coins, int coin_num, int price) {
if (price <= 0) {
return 0;
}
int min_coins = INT_MAX;
for (int i = 0; i < coin_num; i++) {
if (price >= coins[i]) {
int previous = get_min_coins_recursive(coins, coin_num, price - coins[i]);
if (previous != INT_MAX) {
min_coins = min_int(previous + 1, min_coins);
}
}
}
return min_coins;
}找零递归：展开最后一枚硬币的选择
解锁完整互动实验、进阶解析与精选参考答案。
动态规划的另一个组成部分就是状态转移方程：
其次需要考虑初始条件和边界情况。如果不能拼出i元，则定义。例如当、、小于0时：
状态转移方程的初始状态为F[0] = 0，因为无需任何硬币就能拼成0元。
知识测验
最少硬币：比较候选、写入状态、回溯方案
解锁完整互动实验、进阶解析与精选参考答案。
硬币找零（动态规划）
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
static int min_int(int a, int b) {
return a < b ? a : b;
}
int get_min_coins_dp(int *coins, int coin_num, int price) {
int dp[price + 1];
dp[0] = 0;
for (int i = 1; i <= price; i++) {
dp[i] = INT_MAX;
for (int j = 0; j < coin_num; j++) {
if (i >= coins[j] && dp[i - coins[j]] != INT_MAX) {
dp[i] = min_int(dp[i - coins[j]] + 1, dp[i]);
}
}
}
return dp[price];
}硬币面值为正整数，金额为非负整数；无法凑出时，Python返回∞，C/C++/Java返回各自整数类型的最大值。
知识测验
求新面值的最少硬币
目标11。定义状态和边界，计算F(0)到F(11)，为每个有限状态记录最后一枚硬币，回溯一个最少硬币组合。无法凑出的状态保留∞。