这道题先用搜索写的，因为我需要先打表来寻找规律。
因为数据量小所以收搜也会过
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int num[];
int sum, ans;
void dfs(int cur, int n, int m)
{
if (n == sum)
{
ans++;
}
else if (cur>m)return;
else
{
for (int i = ; i <= n; ++i)
{
if (num[cur - ] <= i)
{
sum += i;
if (sum <= n){
num[cur] = i;
dfs(cur + , n, m);
}
sum -= i;
}
}
}
}
int main()
{
int t,n, m;
scanf("%d", &t);
while (t--)
{
sum = ans=;
scanf("%d%d", &n, &m);
dfs(, n, m);
printf("%d\n", ans);
}
}
然后：寻找规律，凡是dp和递推题，当想不到动态转移方程时，就应该先打表再推表达式
#include<iostream>
#include<cstdio>
using namespace std;
int dp[][];
int main()
{
//一个盘子，无论苹果
for (int i = ; i < ; ++i)dp[i][] = ;
//0个苹果，无论多个盘子
for (int j = ; j < ; ++j)dp[][j] = ;
for (int i = ; i < ;++i)
for (int j = ; j < ;++j)
if (i >= j)dp[i][j] = dp[i][j - ] + dp[i - j][j];
else dp[i][j] = dp[i][i];
int t, n, m;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
printf("%d\n", dp[n][m]);
} }