[NOIP2001]数的划分

DFS

#include<bits/stdc++.h>
using namespace std;
int n,k,res;
struct Num {int now,cnt;
};
void DFS(Num num,int pos) {//DFS遍历if(num.cnt==1&&num.now>=pos) {//最后一次递归的时候++res;return ;}for(int i=(pos?pos:1); i<=num.now; ++i) {//按照单调不减序列排DFS({num.now-i,num.cnt-1},i);//递归为将now-i这个数划分为cnt-i份，每份不为空}
}
int main() {scanf("%d%d",&n,&k);DFS({n,k},0);printf("%d\n",res);
}

动态规划

#include<bits/stdc++.h>
using namespace std;
#define M 500
int n,k;
int dp[M][M];
void init() {for(int i=1; i<=n; ++i) {dp[i][1]=1;//dp初始化}
}
int main() {scanf("%d%d",&n,&k);init();for(int i=2; i<=n; ++i) {for(int j=2; j<=k; ++j) {if(i>j)dp[i][j]=dp[i-1][j-1]+dp[i-j][j];//先对j个分块预置为1else dp[i][j]=dp[i-1][j-1];//依次拿一个数出来}}printf("%d\n",dp[n][k]);
}