可以证明，有且仅有 n=1,3 无解。显然因为有 2 故偶数均有解。\forall x\ge 5,x\in N，其至少可以拆分为 x=5+y，其中 y 是零或偶数。
直观上看，要使得解最优，一定会以 7\to 5\to 2 的优先级取硬币。
通过打表，可以直观地发现，当 n \ge 14 时，数字每七个一组呈现出规律性，对 n=7k+0,7k+1,\cdots,7k+6，答案为 k,k+1,k+1,k+1,k+2,k+1,k+2。根据该规律可以求解出答案(n < 14 特判)。复杂度 O(1)。
#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%lld", &x)
typedef long long ll;
ll n, a[] = {-1, -1, 1, -1, 2, 1, 3, 1, 4, 2, 2, 3, 2, 4, 2}, t;
ll r[] = {0, 1, 1, 1, 2, 1, 2};
signed main()
{
for (sc(t); t; t--)
{
sc(n);
if (n < 14)
{
printf("%lld\n", a[n]);
continue;
}
printf("%lld\n", n / 7 + r[n % 7]);
}
return 0;
}
严格证明：根据无限背包 DP 的表达式，可知： dp_i=1+\min(dp_{i-2},dp_{i-5},dp_{i-7}) 首先根据暴力计算，可知 [0,14) 内 dp_{7k+r} 答案如下表：
| 倍数k\余数r | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | / | / | 1 | / | 2 | 1 | 3 |
| 1 | 1 | 4 | 2 | 2 | 3 | 2 | 4 |
可以先根据前面无规律的结果暴力求解出第二列：
| 倍数k\余数r | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 2 | 2 | 3 | 3 | 3 | 4 | 3 | 4 |
直观计算，对 x=3，分类讨论：
更一般地，假设我们已知 dp 的前七项 dp_{7(k-1)+r} 为 k,k+1,k+1,k+1,k+2,k+1,k+2
那么跟上面分类讨论同理的做法，可以求得下七项 dp_{7k+r} 为
k+1,k+2,k+2,k+2,k+3,k+2,k+3
即： \begin{cases} dp_{k\cdot7+0} &=1+\min(dp_{(k-1)\cdot7+5}+dp_{(k-1)\cdot7+2}+dp_{(k-1)\cdot7+0}) =1+\min(k+1k+1k)=k+1 \\ dp_{k\cdot7+1} &=1+\min(dp_{(k-1)\cdot7+6}+dp_{(k-1)\cdot7+3}+dp_{(k-1)\cdot7+1}) =1+\min(k+2k+1k+1)=k+2 \\ dp_{k\cdot7+2} &=1+\min(dp_{k\cdot7+0}+dp_{(k-1)\cdot7+4}+dp_{(k-1)\cdot7+2}) =1+\min(k+1k+2k+1)=k+2 \\ dp_{k\cdot7+3} &=1+\min(dp_{k\cdot7+1}+dp_{(k-1)\cdot7+5}+dp_{(k-1)\cdot7+3}) =1+\min(k+2k+1k+1)=k+2 \\ dp_{k\cdot7+4} &=1+\min(dp_{k\cdot7+2}+dp_{(k-1)\cdot7+6}+dp_{(k-1)\cdot7+4}) =1+\min(k+2k+2k+2)=k+3 \\ dp_{k\cdot7+5} &=1+\min(dp_{k\cdot7+3}+dp_{k\cdot7+0}+dp_{(k-1)\cdot7+5}) =1+\min(k+2k+2k+1)=k+2 \\ dp_{k\cdot7+6} &=1+\min(dp_{k\cdot7+4}+dp_{k\cdot7+1}+dp_{(k-1)\cdot7+6}) =1+\min(k+3k+2k+2)=k+3 \\ \end{cases} 那么根据数学归纳法，可以得出结论：k\ge 2,r\in[0,6],k,r\in Z 时，有： dp_{7k+r}={k,k+1,k+1,k+1,k+2,k+1,k+2}
TODO: 能否将 O(1) 推广到较为一般的情况，对小的 n 或互质的 a，总能找出一个通式，
从而取代无限背包