#include <bits/stdc++.h>
using namespace std;
int n;
int f[1000010];//储存答案
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        f[i]=1+f[i-1];
        if(i>=5)
            f[i]=min(f[i],1+f[i-5]);
        if(i>=11)
            f[i]=min(f[i],1+f[i-11]);//寻找所有方案中的最优解
    }
    cout<<f[n]; 
    return 0;
}

用f[i]表示凑出i元所需的硬币数量，那么初始状态是f[0]=0，f[i]可以通过f[i-1]+1, f[i-5]+1, f[i-11]+1取最小值得到。需要注意下标不能取到负数。

f[0] = 0;
for (int i = 1; i <= n; i++) {
	f[i] = f[i - 1] + 1;
	if (i >= 5)
		f[i] = min(f[i], f[i - 5] + 1);
	if (i >= 11)
		f[i] = min(f[i], f[i - 11] + 1);
}
cout << f[n];

用递归，光荣牺牲……递推终于扳回一局😄

递归的惨象！！

状态分数 耗时 内存占用

#1	 Time Exceeded0	≥1067ms	≥4.4 MiB
#2	 Time Exceeded0	≥1067ms	≥4.1 MiB
#3	 Time Exceeded0	≥1067ms	≥3 MiB
#4	 Time Exceeded0	≥1067ms	≥3.9 MiB
#5	 Time Exceeded0	≥1067ms	≥2.5 MiB
#6	 Time Exceeded0	≥1067ms	≥3.2 MiB
#7	 Time Exceeded0	≥1067ms	≥1.4 MiB
#8	 Time Exceeded0	≥1067ms	≥2.2 MiB
#9	 Time Exceeded0	≥1067ms	≥376 KiB
#10	 Time Exceeded0	≥1067ms	≥1.5 MiB

代码：

#include <bits/stdc++.h>
using namespace std;
int u[1000005];
int main()
{
    int n;
    cin >> n;
    for (int i = 1;i <= 11;i++)
    {
        u[i] = i / 5 + i % 5;
        if (i == 11) u[i] = 1;
    }
    for (int i = 12;i <= n;++i)
    {
        u[i] = min(min(u[i - 1],u[i - 5]),u[i - 11]) + 1;
    }
    cout << u[n];
}