整数拆分

先记录一下动态规划得思想：动态规划和分治法很像。分治法是把大问题拆分成小问题解决，但是小问题经常重复被解决，所以耗时很长；动态规划也是把大问题拆分成小问题，但是小问题都被记录下来，不会重复被解决，所以效率很高。
动态规划的任务就是填表。填表的顺序是从左到右，从上到下，即这个表是个二维数组。以背包问题为例，在填写每一行时，随着列的增加，意味着背包的容量的增加；而在同一列中，随着行的增加，意味着在这个容量下（列不变）背包能装的东西的种类的增加（行变）。
接下来我们来看一下这道题，输入一个数n，然后看看由2^0,2^1,2^2,...,2^n组成的方案一共有多少种。这就可以想成：我有一个容量为n的背包，现在有价值为2^0,2^1,2^2,...,2^n的物品（这里很明显物品的价值和占的空间大小是一样的），我用这些物品填充我的背包，一共有多少种方案？（这里每个种类的物品都有无数个）
对于容量为n的背包，我们逐渐增加物品种类来分析：
1、当只有种类为2^0的物品时：那么背包只能由n个1填充了；
2、当种类有2^0,2^1的物品时，背包有有几种填充情况呢？答案是有：（原本只有2^0的物品时背包的填充方案数量）+（背包容量为n-2^1时的填充方案）。可能这里比较难以理解，我来举个例子，我现在有一个容量为4的背包，我前面如果只装1物品的时候，我有1种方案（全1）；这时，我又可以装物品2了，我就把背包分成了两份，一份容量为2（这部分用来放物品2），另一部分容量为4-2。4-2部分的填充情况怎么算呢？仔细想想，这不就是求容量为2的背包的填充情况嘛，用同样的逐渐增加种类的方法不就可以求出来吗？所以，当种类有2^0,2^1的物品时，容量为4的背包的填充方案数量=只有1的物品时的填充方案数量+背包容量为2时的填充方案数量。这里大家别忘了，容量为4的背包还可以放下种类为2^2的物品哦，所以不要认为上面这条式子是错的。
3、当当种类有2^0,2^1,2^2的物品时，填充方案数=（原本只有种类为2^0,2^1的物品时的填充方案数量）+（背包容量-2^2的填充方案数量）
4、接下来逐渐增加物品种类，背包的填充方案也会逐渐地增加。（眼前的妹子越多，我们的选择也越多嘛）

代码实现很短，但是很精妙：

#include<iostream>
using namespace std;

int main()
{
    int n;
    while (cin >> n) {
        int *max = new int[n + 1];
        for (int i = 0; i <= n; ++i)
            max[i] = 1;//这里是只有种类为1的物品时，各容量的背包的填充方案数量（明显都是只能由1组成）
        int k, j;
        for (k = 2; k <= n; k *= 2) {//物品种类增加
            for (j = k; j <= n; ++j) {//j代表了背包的容量，这个循环的意思就是：在有种类为2^1,2^2,...,k的物品时，求容量为j的背包的填充方案数量
                max[j] = max[j] + max[j - k];//精华：翻译成人话就是：
                //容量为j的背包在有有种类为2^1,2^2,...,k的物品时的填充方案数量=
                //容量为j的背包在只有种类为2^1,2^2,...,k/2的物品时的填充方案数量+
                //容量为j-k的背包的填充方案数量
                max[j]%=1000000000;
            }
        }
        cout << max[n] << endl;
    }
    return 0;
}