洛谷1025
简单dp
f[i][j]表示把数i分成j分的方案数，则最终答案为f[n][k]。把f分为两种状态，第一种为分出来的数中最小值为1，即f[i-1][j-1]；另一种为最小值大于一，怎么办呢？可以先在j个位置上放1，再划分，即f[i-j][j]，所以转移方程为f[i][j]=f[i-1][j-1]+f[i-j][j];
#include<iostream> using namespace std; int f[1000][1000]; int n,k; int main() { cin>>n>>k; for(int i=1;i<=n;i++) f[i][i]=1; for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) { if(i>j) f[i][j]=f[i-1][j-1]+f[i-j][j]; } cout<<f[n][k]; return 0; }
原文：http://www.cnblogs.com/war1111/p/7290967.html