08 拼硬币（递归）

题目大意是任意给定一些面值的硬币，然后给定一个金额的数值，问最少用多少枚上述硬币可以拼出指定的金额。

例如，面值为1， 4， 5的三种硬币，拼出面值为13。
有多种拼法：
2枚5，3枚1；
3枚4，1枚1；
2枚4，1枚5（最少硬币）
....

我们就是要计算出任给金额所需要硬币数量最小值。

分析：
刚开始着实被题目难住了，看起来太吓人了，然后思考过筛法，思考过循环....等等。
反正卡了有一段时间。
后面才发现这其实就是很经典的一道状态转移的递归题目：

1. 边界条件：
   n = 4 || 5， 直接返回1（只需要1枚4元或者5元硬币）
   n < 4，直接返回n（需要n枚1元硬币）

2. 状态转移方程：
   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