題目描述
一個整數(shù)總可以拆分為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的不同拆分的種數(shù)耗溜，例如f(7)=6. 要求編寫程序痴鳄，讀入n(不超過1000000)昆著，輸出f(n)%1000000000。
輸入描述:
每組輸入包括一個整數(shù)：N(1<=N<=1000000)术陶。
輸出描述:
對于每組數(shù)據(jù)凑懂，輸出f(n)%1000000000。
示例1
輸入
7
輸出
6
思路一
設(shè)對于一大于1的整數(shù)n梧宫，f(n)表示其拆分方式個數(shù)接谨，由于是拆分為2的冪的和，所以n由1塘匣、2脓豪、4、8...組成
所以可以觀察到忌卤，
（1）如果 n 是奇數(shù)扫夜，那么 n 與 n - 1 的拆分方式個數(shù)相同，
這是因為此時 n 的拆分形式中一定會有一個 1，不然組成不了奇數(shù)笤闯，即
n 的拆分形式恒為 1 + (n - 1)
所以n的拆分方式個數(shù)取決于 n - 1 的拆分方式個數(shù)堕阔，即 f(n) = f(n - 1)
（2）如果 n 是偶數(shù)，那么 n 的拆分形式可以劃分為兩種形式颗味，第一種是包含有1的形式超陆，即
n == 1 + (n - 1)，此時 n 的拆分形式個數(shù)取決于 n - 1 的拆分形式個數(shù)
第二種是不含有1的形式浦马，即
n == n / 2 + n / 2时呀，此時 n 的拆分形式個數(shù)取決于 n / 2 的拆分形式個數(shù)
這兩種形式不相交，且包含了所有的情況晶默，即 f(n) = f(n - 1) + f(n / 2)谨娜，對于任何一個 n，最終都會退化到求 f(1)荤胁，而 f(1) = 1
綜合上面兩種情況瞧预，代碼便呼之欲出了
解法一
#include<stdio.h>
int main(){
int n = 0; //待輸入的數(shù)
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;
}
思路二
解法一采用的是觀察出來的遞推公式求解的，接下來思考用動態(tài)規(guī)劃求解仅政，動態(tài)規(guī)劃一般是用來求解一個最優(yōu)解垢油，在求解一個最優(yōu)解的過程中，會求出所有的解圆丹，所以可以用來計算這道題
抱歉滩愁，還未想到怎么做，等我去后面刷一下專門的DP題目辫封，再回來思考這道題
