【动态规划】POJ 2229

题目地址：http://poj.org/problem?id=2229

题目大意

大致题意是，一个数N能有几种拆分方式，拆分的数字必须是2的幂。

思路

刚开始用母函数试了一下，果断超时2333。。。

还是动态规划找下规律吧。

首先考虑N为奇数，奇数的话必然都是1开头，例如7

1+1+1+1+1+1+1 = 7
1+1+1+1+1+2
1+1+1+2+2
1+1+1+4
1+2+2+2
1+2+4

把所有的1去掉，即

1+1+1+1+1+1 = 6
1+1+1+1+2
1+1+2+2
1+1+4
2+2+2
2+4

则此时和为6，也就是说，若N为奇数，则拆分数和N-1(偶数)的拆分数一样。

若N为偶数，则必然有两种情况：1开头和2开头，例如上面的6。而1开头的拆分数和N-1（奇数）的拆分数加上2开头的拆分数。将所有2开头的拆分数除以2，则数量和N/2的拆分数一致。例如6以2开头的拆分数（就是6/2=3的拆分数）：

$2+2+2 => 1+1+1 = 3$
$2+4 => 1+2$

综上所述，有$dp[N] = dp[N-1] + dp[N\%2==0?N/2:0]$

AC代码

/*************************************************************************
    > File Name: 2229.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-09-20 日 15:42:21 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int N;
int a[1000005];

void solve() {
    a[1] = 1;
    a[2] = 2;
    for(int i=3; i<=N; ++i)
        a[i] = (a[i-1] + (i%2==0 ? a[i/2] : 0)) % 1000000000;
    cout << a[N] << endl;
}

int main()
{
#ifdef Oj
    // freopen(".in", "r", stdin);
#endif
    cin.sync_with_stdio(false);
    cin >> N;
    solve();
    return 0;
}