题目链接：http://acm-software.hrbust.edu.cn/problem.php?id=1472
题意：给n个硬币，面值随意。问恰好凑成m元的种类数（去掉重复）。
dp(i,j,k)表示i个硬币，j元，最大是k时的种类数。
一开始智障记忆化dfs暴T不止，转成递推还是会T。
结果就考虑先给记忆化dfs加一些剪枝，还是T。
再给递推做一些处理，发现是因为枚举当前最大的时候，最大的l如果是j+2了，即使只有它一个，也是大于j+1了。换到这里来看，是前向着递推，那也就是说，题目所述最小面值是1，在递推的时候仅仅维持在j内是不满足的，需要j+1。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = ;
const int maxn = ;
LL dp[maxn][maxn][maxn];
int n, m; LL dfs(int n, int m, int pre) {
if(dp[n][m][pre] != -) return dp[n][m][pre];
// if(pre > m) return dp[n][m][pre] = 0;
if(n == ) {
if(m == ) return dp[n][m][pre] = ;
return dp[n][m][pre] = ;
}
dp[n][m][pre] = ;
for(int i = pre; i <= m; i++) {
if(m - i < ) break;
dp[n][m][pre] = (dp[n][m][pre] + dfs(n-, m-i, i)) % mod;
}
return dp[n][m][pre];
} int main() {
// freopen("in", "r", stdin);
int T;
scanf("%d", &T);
memset(dp, , sizeof(dp));
dp[][][] = ;
for(int i = ; i <= ; i++) {
for(int j = ; j <= ; j++) {
for(int k = ; k <= ; k++) {
if(dp[i][j][k] == ) continue;
for(int l = k; j + l <= ; l++) {
if(l > j + ) break;
dp[i+][j+l][l] = (dp[i+][j+l][l] + dp[i][j][k]) % mod;
}
}
}
}
while(T--) {
scanf("%d%d",&n,&m);
LL ret = ;
for(int i = ; i <= m; i++) {
ret = (ret + dp[n][m][i]) % mod;
}
printf("%lld\n", ret);
}
return ;
}