7-14 整数拆分——递归/推

给定一个整数n，将其无序拆分成最大数为k的拆分数，（n,k不超出100）
要求：所有的拆分方案不重复。
如当n=4,k=4时，一共有5种拆分方案，拆分如下：

(1)4=1+1+1+1
(2)4=1+1+2
(3)4=1+3
(4)4=2+2
(5)4=4
输入格式:
每一行输入一组整数n,k，遇到键盘结束符^Z或文件结束符EOF时结束输入。

输出格式:
按行输出每组的拆分方案数。

输入样例:
4,4
5,4
输出样例:
5
6

分析

思路：

1. n == 1 || k == 1，拆分只有一种情况
2. n < k，相当于拆分f(n,n)
3. n == k，n可以拆分为包含k的式子，只有1种方法；也可以不包含k，那就是拆分f(n,k-1)；两种方案相加
4. n > k，n也是可以拆分为包含k的式子，有f(n-k,k)种方法；也可以不包含k，那就是拆分为f(n,k-1)；两种方案相加

递归（TLE）

直接递归TLE，毕竟n=100左右呢，递归都爆栈，但是在这个题的思想重要；

#include

using namespace std;

int f(int n, int k) {
    if (n == 1 || k == 1) {
        return 1;
    } else if (n < k) {
        return f(n, n);
    } else if (n == k) {
        //包含k就1种，不包含k
        return f(n, k - 1) + 1;
    } else {//n>k
        //包含k，不包含k
        return f(n - k, k) + f(n, k - 1);
    }
}

int main() {
    int n, k;
    while (cin >> n) {
        getchar();
        cin >> k;
        cout << f(n, k) << endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

递推（AC）

把上面递归转化为递推(dp)，暴力枚举每种情况计算即可；

#include

using namespace std;

int f[105][105];

void solve(int n, int k) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            if (i == 1 || j == 1) {
                f[i][j] = 1;
            } else if (i < j) {
                f[i][j] = f[i][i];
            } else if (i == j) {
                f[i][j] = f[i][j - 1] + 1;
            } else {
                f[i][j] = f[i - j][j] + f[i][j - 1];
            }
        }
    }
}

int main() {
    int n, k;
    while (cin >> n) {
        getchar();
        cin >> k;
        solve(n, k);
        cout << f[n][k] << endl;
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34