poj 2229 拆数问题 dp算法

题意：一个n可以拆成 2的幂的和有多少种

思路：先看实例

1 1

2 1+1 2

3 1+1+1 1+2

4 1+1+1+1 1+1+2 2+2 4

5 1+1+1+1+1 1+ 1+1+2 1+2+2 1+4

对于奇数：相当于前面一个偶数的每一种情况的开头+1 dp[i]=dp[i-1]
对于偶数分两种情况开头是1的相当于 dp[i-1] 开头没有1的相当于 dp[i/2]的情况

解决问题的代码：

#include <iostream>

#include <algorithm>

#include <cstdio>

using namespace std;

int dp[];

int main()

{

        int n;

        dp[] = ;

        scanf("%d", &n);

        for (int i = ; i <= n; i++)

        {

               if (i %  == ) dp[i] = dp[i - ];

               else dp[i] = (dp[i - ] + dp[i / ])% ;

        }

        printf("%d\n", dp[n]);

        return ;

}

巴特西

poj 2229 拆数问题 dp算法

最新文章

热门文章