7. 整数拆分

题目描述

一个整数总可以拆分为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。

示例1

输入

7

输出

6

---

思路一

设对于一大于1的整数n，f(n)表示其拆分方式个数，由于是拆分为2的幂的和，所以n由1、2、4、8...组成

所以可以观察到，
（1）如果 n 是奇数，那么 n 与 n - 1 的拆分方式个数相同，
这是因为此时 n 的拆分形式中一定会有一个 1，不然组成不了奇数，即

n 的拆分形式恒为 1 + (n - 1)

所以n的拆分方式个数取决于 n - 1 的拆分方式个数，即 f(n) = f(n - 1)

（2）如果 n 是偶数，那么 n 的拆分形式可以划分为两种形式，第一种是包含有1的形式，即

n == 1 + (n - 1)，此时 n 的拆分形式个数取决于 n - 1 的拆分形式个数

第二种是不含有1的形式，即

n == n / 2 + n / 2，此时 n 的拆分形式个数取决于 n / 2 的拆分形式个数

这两种形式不相交，且包含了所有的情况，即 f(n) = f(n - 1) + f(n / 2)，对于任何一个 n，最终都会退化到求 f(1)，而 f(1) = 1

综合上面两种情况，代码便呼之欲出了

解法一

#include<stdio.h>

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

思路二

解法一采用的是观察出来的递推公式求解的，接下来思考用动态规划求解，动态规划一般是用来求解一个最优解，在求解一个最优解的过程中，会求出所有的解，所以可以用来计算这道题
抱歉，还未想到怎么做，等我去后面刷一下专门的DP题目，再回来思考这道题