哦，K个数,指的也是正整数.

组合学里的东西 看我的兴趣小组

这个能用DP吗

DP？

DP是求最优解，这里不是最优化问题，是组态的记数。

首先先创建一个集合，元素个数为N-1，并且给其赋初值1、2、… N-1，这样就构成了一个比N小的正整数的所有集合，标记这个集合为A，那么就可以通过求这个A集合的元素个数为K的子集来实现求解。求这个A集合K个元素的子集合的方法可以通过回朔法求得。算法需要额外的N - 1个单位空间和2的K次方的时间复杂度

回复5楼的:
你提到的解法跟我提的问题不一样.我是一个正整数的划分数,而不是求一集合里K个元素子集的个数。如果硬要按你的算法，复杂度就够呛,还得进一步筛选符合条件的，根本是不可能的事.
回复2楼的:
"一个整数n拆分成恰好m部分的拆分数等于这个整数n拆分成最大部分为m的拆分数."
我去看了下，大有所获,谢谢!这样求解这个问题就可以转换成DP来解了。
a[n][k]表示整数N划分为最大数不超过K的划分数.
a[n][k]=a[n-k][k]+a[n][k-1];
则原问题就是求解a[n-k][k]了.这样就很容易解决了!

可以说，没有min和max就不是DP，运筹学里的规划方法都是求最优决策。

貌似和金山公司的那道分苹果一样

// 正整数n划分为k个正整数的和的划分数
// 使用递归

#include <iostream>
using namespace std;

const int MAXK=10;
int n, k, total, a[MAXK];

void print() {
    int i=0;
    while(true) {
        cout<<a[i];
        if(a[++i] != 0)
            cout<<'+';
        else
            break;
    }
    cout<<endl;
}

void divide(int n, int k, int min, int index) {
    while(min<=n/k) {
        if(k>1) {
            a[index]=min;
            divide(n-min,k-1,min,index+1);
        }
        else {
            a[index]=n;
            total++;
            print();
            return;
        }
        min++;
    }
} 

int main() {
    while(true) {
        cout<<"请输入n、k"<<endl;
        do {
            cin>>n>>k;
        } while(n<0 || k<0);
        if(n==0 || k==0)
            break;
        memset(a,0,sizeof(a));
        total=0;    
        divide(n,k,1,0);
        cout<<"total="<<total<<endl<<endl;
    }
}

[quote]a[n][k]表示整数N划分为最大数不超过K的划分数.
a[n][k]=a[n-k][k]+a[n][k-1];
则原问题就是求解a[n-k][k]了.这样就很容易解决了![/quote]

这个公式不错，边界是a[n][1]=a[1][n]=a[0][n]=1，n*k次加法完成。