题目描述
rt
样例
rt
算法1
(dfs暴搜) $O(n^2)$
dsf的关键在于构造递归树,index表示当前枚举到的第index个位置,st表示当前第index个位置的值,(通过单调不减保证不重复),sum表示枚举到当前位置的总和
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int res;
int m,n;
void dfs(int index,int st,int sum){
if(index==n) {
if(sum==m){
res++;
}
return;
}
for(int i = st;i<=m-sum;i++){
dfs(index+1,i,sum+i);
}
}
int main(){
int T;
cin>>T;
while(T--){
cin>>m>>n;
res = 0;
dfs(0,0,0);
cout<<res<<endl;
}
}
算法2
(DP) $O(n^2)$
时间复杂度
参考文献
C++ 代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 11;
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
int n, m;
scanf("%d%d", &m, &n);
int f[N][N] = {0};
f[0][0] = 1;
for (int i = 0; i <= m; i ++ )
for (int j = 1; j <= n; j ++ )
{
f[i][j] = f[i][j - 1];
if (i >= j) f[i][j] += f[i - j][j];
}
printf("%d\n", f[m][n]);
}
return 0;
}