【清华考研】整数划分

发表于 | 更新于 | 分类于

1. 题目描述

  • 题目描述

一个整数总可以拆分为2的幂的和，例如： 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。 再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。 用f(n)表示n的不同拆分的种数，例如f(7)=6. 要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。

  • 输入描述 每组输入包括一个整数：N(1<=N<=1000000)。

  • 输出描述 对于每组数据，输出f(n)%1000000000。

题目链接

2. 初步分析与实现

2.1 递推式

这道题其实就是以前讲过的整数划分问题的一个变种。这道题的递推公式就是稍微变了一下而已，我们令 \(f(n, m)\) 表示用最大为 m 的数来组成 n，则有公式:

\[ \begin{cases} &f(n, m) = f(n, \frac{m}{2}) + f(n - m, m)\\ &m = 2^i \end{cases} \]

简单地分析一下初始条件，可以得到初版的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int resolve(int n, int m)
{
    if (n <= 0 || m <= 0)
        return 0;
    else if (n == 1 || m == 1)
        return 1;
    if (n == m)
        return resolve(n, m / 2) % C + 1;
    if (n < m)
    {
        m = (int)log2(1.0 * n);
        m = exp2(1.0 * m);
    }
    int a = resolve(n, m / 2) % C;
    int b = resolve(n - m, m) % C;
    return (a + b) % C;
}

纯递归的方式肯定会超时，需要变成动态规化的形式。

2.2 DP初版

这个式子直接变成动态规划的形式有点麻烦，因为 \(m\) 需要为 2 的阶乘，这就意味着如果我们令 \(dp[n][m] = f(n, m)\)，那么二维数组 dp 中会有一大部分空间被浪费，所以我们做一点空间压缩，令:

\[ dp[n][2^j] = f(n, m) \]

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
int C = 1000000000;
const int N = 1000001;
const int M = (int)log2(1.0 * N) + 1;
int dp[N][M];

void DP()
{
    //n == 1, 2 ^ m = 1
    for (int i = 0; i < M; ++i)
        dp[0][i] = dp[1][i] = 1;
    for (int i = 1; i < N; ++i)
        dp[i][0] = 1;

    int a, b;
    int m, logM;
    for (int j = 1; j < M; ++j)
    {
        for (int n = 2; n < N; ++n)
        {
            logM = j;
            m = (int)exp2(logM);
            if (n < m)
                continue;
            a = dp[n][j - 1] % C;
            b = dp[n - m][j] % C;
            dp[n][j] = (a + b) % C;
        }
    }
}

3. 使用滚动数组

那么这道题就这么结了吗？并非如此，如果用上面的代码跑一下会发现结果是内存超限了。原因在于即使压缩了空间，这个二维数组还是太大了。所以需要进一步压缩空间，这里就需要用到名为滚动数组的技巧了。

3.1 滚动数组介绍

滚动数组的作用在于优化空间，主要应用在递推或动态规划中（如01背包问题）。因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。

举一个简单的例子，斐波那契数列。

1
2
3
4
5
6
7
8
9
10
11
int Fib[25];
 
int fib(int n)
{
    Fib[0] = 0;
    Fib[1] = 1;
    Fib[2] = 1;
    for(int i = 3; i <= n; ++i)
        Fib[i] = Fib[i - 1] + Fib[i - 2];
    return Fib[n];
}

我们发现实际上要用到的空间远远没有 n 个，利用滚动数组优化后代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Fib[3];
 
int fib(int n)
{
    Fib[1] = 0; 
    Fib[2] = 1;
    for(int i = 2; i <= n; ++i)
    {
        Fib[0] = Fib[1]; 
        Fib[1] = Fib[2];
        Fib[2] = Fib[0] + Fib[1];
    }
    return Fib[2];
}

这个“滚动”可以说是很形象了。

3.2 使用滚动数组优化

要使用滚动数组优化空间，我们就需要搞清楚哪些空间是用得到的，哪些是用不到的，仔细观察状态转移式子:

1
2
3
a = dp[n][j - 1] % C;
b = dp[n - m][j] % C;
dp[n][j] = (a + b) % C;

我们发现，在写入 dp[n][j]，时需要的老信息只有两个:

  • 同为 j 列的数据
  • dp[n][j - 1]

也就是说 dp[:][0:j-1] 和 dp[1:n][j-1] 的数据都是不用管的老数据。我们可以只保留 2 列数据，并且在迭代中不断把这两行数据往右“滚动”。

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
35
int dp[N][2];
void DP()
{
    //n == 1, 2 ^ m = 1
    for (int i = 0; i < 2; ++i)
        dp[0][i] = dp[1][i] = 1;
    for (int i = 1; i < N; ++i)
        dp[i][0] = 1;
    int a, b;
    int m;
    for (int j = 1; j < M; ++j)
    {
        for (int n = 2; n < N; ++n)
        {
            m = (1 << j);
            if (n < m)
                continue;
            a = dp[n][0] % C;
            b = dp[n - m][1] % C;
            dp[n][1] = (a + b) % C;
            //滚动
            dp[n][0] = dp[n][1];
        }
    }
}
int main()
{
    int n = 0;
    DP();
    while (cin >> n)
    {
        cout << dp[n][1] << endl;
    }
    return 0;
}