题解 | 整数拆分

#include <bits/stdc++.h>
#include <cstring>
using namespace std;

const int SIZE=1000001;
int dp[SIZE];

int main(){
    int n;
    dp[0]=1;
    while(cin>>n){
        for(int i=1;i<=n;i++){
            if(i%2==0)dp[i]=(dp[i-1]+dp[i/2])%1000000000;
            else dp[i]=dp[i-1]%1000000000;
        }
        cout<<dp[n]<<endl;
    }
}

本题我是这么做的，用数学推演，得到的结论，首先，我们可以知道规则，一定是拆解成2的幂，所以，可以发现一点，无论奇偶，都可以进行拆出来1的操作，这时候，就一定变成了前一个数的情况，但是，对于偶数，我们可以知道，他是可以不拆出来1的，那么我们因为数学特性和题目要求，一定可以拆出来2，那么我们剩下的组分其实就是2的倍数的组合，那么把这个2提出去，就是n/2,也就是额外的组合数量dp[n/2]，就得到了上述方程，我认为目前的类似题解都分析错了。#牛客创作赏金赛#