题解 | #整数拆分#

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin>>N;
    int dp[N+1];//dp[i]=整数i的拆分种数
    dp[1]=1;//整数1只有一种拆分方式
    dp[2]=2;//整数2可以有两种拆分方式
    for(int i=3;i<=N;i++)
    {
        //1.如果是奇数，拆分中一定包含1，只要dp[i/2]中每种拆分方式都加个1，就肯定包含1
        if(i%2==1)
        {
            dp[i]=dp[i-1]%1000000000;
        }
        //2.如果是偶数，有且仅有两种可能，包含1或者不包含1
        //dp[i-1]是包含1的种类,原因同上
        //dp[i/2]是不包含1的拆分方式数目，只要dp[i/2]中每种拆分方式中的每个元素都×2，就肯定不包含1
        else {
            dp[i]=(dp[i-1]+dp[i/2])%1000000000;
        }
    }
    cout<<dp[N];
}
// 64 位输出请用 printf("%lld")