题解 | #整数拆分#
整数拆分
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;
}
