题目大意是任意给定一些面值的硬币，然后给定一个金额的数值，问最少用多少枚上述硬币可以拼出指定的金额。
例如，面值为1， 4， 5的三种硬币，拼出面值为13。
有多种拼法：
2枚5，3枚1；
3枚4，1枚1；
2枚4，1枚5（最少硬币）
....
我们就是要计算出任给金额所需要硬币数量最小值。
分析：
刚开始着实被题目难住了，看起来太吓人了，然后思考过筛法，思考过循环....等等。
反正卡了有一段时间。
后面才发现这其实就是很经典的一道状态转移的递归题目：
边界条件：
n = 4 || 5， 直接返回1（只需要1枚4元或者5元硬币）
n < 4，直接返回n（需要n枚1元硬币）状态转移方程：
f(n) 只可能从以下三种情况转移得到（三种情况是或者的关系）：
f(n - 1) + 1（加一枚1元硬币）
f(n - 4) + 1（加一枚4元硬币）
f(n - 5) + 1（加一枚5元硬币）
因为我们要求的是选出数量最少的硬币，那么我们仅仅需要在上述三种状态中选出数量最少的一种即可（因为后面都是加的1，仅仅是前面不同）
那么我们由上述分析可知：状态转移方程为：
f(n) = min(f(n - 1), f(n - 4), f(n - 5)) + 1
image.png
代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int MAX = 1e8;
int dp[MAX];
int get_solutions(int n) {
if (n < 4) return n;
if (n == 4 || n == 5) return 1;
if (dp[n]) return dp[n];
return dp[n] = min(min(
get_solutions(n - 1), get_solutions(n - 4)), get_solutions(n - 5)) + 1;
}
void solve(int n) {
int ans = get_solutions(n);
printf("%d\n", ans);
}
int main(int argc, char const *argv[])
{
int n;
scanf("%d", &n);
solve(n);
return 0;
}
image.png
