题解 | #整数拆分#

整数拆分

https://www.nowcoder.com/practice/376537f4609a49d296901db5139639ec

解决本题目的关键在于:
对于1的处理即划分是否包含1.
#include <iostream>
using namespace std;
#define MAXN 1000001
int main(){
    long long N=0;
    cin>>N;
    //dp数组初始化
    int dp[MAXN]={0};
    dp[1]=1;
    for(int i=2;i<=N;i++){
        if(i%2==0){//i为偶数
            dp[i]=(dp[i-1]+dp[i/2])%1000000000;//拆分为包含1(1的个数一定为偶数个)和不含1的两种情形
        }
        else{//i为奇数
            dp[i]=dp[i-1]%1000000000;
        }
    }
    cout<<dp[N]<<endl;
}


全部评论

相关推荐

每晚夜里独自颤抖:这个在牛客不是老熟人了吗
点赞 评论 收藏
分享
Gaynes:查看图片
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务