[数据结构与算法]【牛客网】KY8 整数拆分

思路一：记f(n)为n的划分数，我们有递推公式：

f(2m + 1) = f(2m)，
f(2m) = f(2m - 1) + f(m)，
初始条件：f(1) = 1。

证明:
证明的要点是考虑划分中是否有1。

记:
A(n) = n的所有划分组成的集合，
B(n) = n的所有含有1的划分组成的集合，
C(n) = n的所有不含1的划分组成的集合，
则有: A(n) = B(n)∪C(n)。

又记:
f(n) = A(n)中元素的个数，
g(n) = B(n)中元素的个数，
h(n) = C(n)中元素的个数，
易知: f(n) = g(n) + h(n)。

以上记号的具体例子见文末。

我们先来证明: f(2m + 1) = f(2m)，
首先，2m + 1 的每个划分中至少有一个1，去掉这个1，就得到 2m 的一个划分，故 f(2m + 1)≤f(2m)。
其次，2m 的每个划分加上个1，就构成了 2m + 1 的一个划分，故 f(2m)≤f(2m + 1)。
综上，f(2m + 1) = f(2m)。

接着我们要证明: f(2m) = f(2m - 1) + f(m)，
把 B(2m) 中的划分中的1去掉一个，就得到 A(2m - 1) 中的一个划分，故 g(2m)≤f(2m - 1)。
把 A(2m - 1) 中的划分加上一个1，就得到 B(2m) 中的一个划分，故 f(2m - 1)≤g(2m)。
综上，g(2m) = f(2m - 1)。

把 C(2m) 中的划分的元素都除以2，就得到 A(m) 中的一个划分，故 h(2m)≤f(m)。
把 A(m) 中的划分的元素都乘2，就得到 C(2m) 中的一个划分，故 f(m)≤h(2m)。
综上，h(2m) = f(m)。

所以: f(2m) = g(2m) + h(2m) = f(2m - 1) + f(m)。

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1e6 + 10;

int main(){
    int n;
    int ans[N];
    ans[0] = ans[1] = 1;
    for(int i = 2; i < N; i++){
        if(i % 2 == 0) ans[i] = (ans[i - 1] + ans[i / 2]) % 1000000000;
        else ans[i] = ans[i - 1] % 1000000000;
    }
    while(scanf("%d", &n) != EOF){
        printf("%d\n", ans[n]);
    }
    return 0;
}

思路二：可以看成是完全背包求恰装满背包时的方案总数问题。具体是，因为每一个拆分必须是1,2,4,2 ^ 3,…2 ^ 19(考虑n最大为10 ^ 6)，所以对于一个整数n，看它的这种拆分数有多少个，就相当于现在有20种物品，第 i 种物品的花费是2 ^ ( i - 1 )，每一种可以重复取，dp[ i ] [ j ]表示前i种物品恰装满容量为 j 的物品时的方案总数,从而dp [ i ] [ j ] = dp[ i - 1 ] [ j ] + dp[ i ] [ j - a [ i ] ]

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N = 1e6 + 10;
int n, dp[N], arr[30];

int main(){
    for(int i = 1; i < 30; i++) arr[i] = 1 << i - 1;
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i = 1; i < 30; i++){
        for(int j = arr[i]; j < N; j++){
            dp[j] += dp[j - arr[i]];
            dp[j] %= 1000000000;
        }
    }
    while(scanf("%d", &n) != EOF){
        printf("%d\n", dp[n]);
    }
    return 0;
}