题目：数的划分
思路：
令f[i][j]为把第i个数分成k份的方案数。
f[i][j]=f[i-1][j-1]+f[i-j][j]
即没有一个数为1的方案数加上有至少一个数为1的方案数。
代码：
dp：
#include<bits/stdc++.h>
using namespace std;#define maxn 200
#define maxm 6int n,m;
int f[maxn+5][maxn+5]= {0};int main() {scanf("%d%d",&n,&m);f[0][0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(i>=j) f[i][j]=f[i-1][j-1]+f[i-j][j];}}printf("%d",f[n][m]);return 0;
}记忆化搜索：
#include<bits/stdc++.h>
using namespace std;#define maxn 200
#define maxm 6int n,m;
int f[maxn+5][maxn+5]= {0};int dfs(int x,int y){if(y==0&&x==0) return 1;if(x<y||x<=0||y<=0) return 0;if(f[x][y]) return f[x][y];f[x][y]=dfs(x-y,y)+dfs(x-1,y-1);return f[x][y];
}int main() {scanf("%d%d",&n,&m);int ans=dfs(n,m);printf("%d",ans);return 0;
}超时代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 200
#define maxm 6int n,m;
int f[maxn+5][maxn+5][maxn+5]= {0};int dfs(int x,int y,int lst){if(y==0&&x==0) return 1;if(x<y||x<=0||y<=0) return 0;if(f[x][y][lst]) return f[x][y][lst];for(int i=lst;i>=1;i--) {f[x][y][lst]+=dfs(x-i,y-1,i);}return f[x][y][lst];
}int main() {scanf("%d%d",&n,&m);int ans=dfs(n,m,n);printf("%d",ans);return 0;
}