学步园

参考 http://www.cppblog.com/bennycen/archive/2011/03/28/142877.html

把一个整数拆分成大于0的整数之和，并且拆分方案不重复。

6
5 + 1 
4 + 2, 4 + 1 + 1
3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

这里，5+1和1+5是同一种分法。

共10种方案

方法1：

对于这种求不重复组合的问题，就是进行有序组合就行了，就是按照升序

int combine(int rem, int curr) {
    if (rem == 0)
        return 1;
    int sum = 0;

    for (;curr <= rem; ++curr)
        sum += combine(rem - curr, curr);

    return sum;
}

cout<<combine(6,1) - 1<<endl;

方法2：

动态规划

首先假设正整数n拆分成k个数(不允许有0)，用f(n,k)表示正整数n拆分成k个数的可行拆分种类的数目。
那么
f(n,n)表示n拆分成n个数(即只有n个1)，显然f(n,n) = 1
然后，可以按照这k份中是否有一份的数为1分成两类：
1)   这k份中没有1份含1的：那么可以在n中拿出k个"1"出来，分到k份中，再将剩下n-k分到k份中，于是这时有
f(n,k) = f(n-k,k)
2)  这k份中至少有一份含有1：首先在n中拿1个"1"出来，再将剩下n-1分到k-1份中，于是这时有：f(n,k) = f(n-1,k-1)

综合起来就是：
f(n,n) = 1
f(n,k) = f(n-k,k) + f(n-1,k-1)

int combine1( int n,int k) {
    
    vector<vector<int> > v(n+1);
    for (int i = 0; i <=n ;++i)
        v[i].resize(k+1,0);
    v[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <=k ; ++j) {
            if (i - j >=0)
                v[i][j] += v[i-j][j];
            if (i - 1 >=0 && j - 1 >=0)
                v[i][j] += v[i-1][j-1];
        }
    }

    int sum = 0;
    for (int i = 2; i <=k ; ++i)
        sum += v[n][i];

    return sum;
}

cout<<combine1(6,6)<<endl;