poj2229 Sumsets (递推)

看到题目能感觉到多半是动态规划，但是没有清晰的思路。

打表找规律：

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<algorithm> 
 5 #include<cstring>
 6 #include<vector>
 7 #include<map>
 8 #include<set>
 9 #define LL long long
10 #define maxn 100005
11 #define MOD 1000000000+7
12 using namespace std;
13 int n, cnt;
14 void dfs(int cur, int k)
15 {
16     if(cur == n){
17         cnt++;
18         return ;
19     }
20     while(cur+k <= n){
21         dfs(cur+k, k);
22         k *= 2;
23     } 
24 }
25 int main()
26 {
27     for(int i = 1; i <= 20; i++){
28         n = i; 
29         cnt=0;
30         dfs(0, 1);
31         cout << cnt << " ";
32     }
33     return 0;
34 }

规律看得出来，但是不知道如何数学描述，也许做多了就有感觉了。看题解分析这个递推的道理，依然觉得很难想到。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<string>
 7 #include<cmath>
 8 #include<vector>
 9 #include<stack>
10 #include<set>
11 #include<iterator>
12 #include<queue>
13 #include<cctype>
14 #include<map>
15 #define lson l, m, rt<<1
16 #define rson m+1, r, rt<<1|1
17 #define IO ios::sync_with_stdio(false);cin.tie(0);
18 #define INF 0x3f3f3f3f
19 #define MAXN 100010
20 const int MOD=1e9;
21 typedef long long ll;
22 using namespace std;
23 int n, ans[1000010];
24 int main()
25 {
26     while(cin >> n){
27         ans[1] = 1;
28         ans[2] = 2;
29         for(int i = 3; i <= n; i++){
30             if(i&1){//奇数的数目和前一个偶数相同（只多一个1） 
31                 ans[i] = ans[i-1];
32             }
33             else{//ans[i-2](多加两个1)+ans[i/2](每位*2) 
34                 ans[i] = (ans[i-2]+ans[i/2])%MOD; 
35             }
36         }
37         cout << ans[n]%MOD << endl;
38     } 
39     return 0;
40 }