0%

NowCoder-整数拆分

Problem

补之前的
一个整数总可以拆分为2的幂的和,例如: 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。 再比如:4可以拆分成:4 = 4,4 = 1 + 1 + 1 + 1,4 = 2 + 2,4=1+1+2。 用f(n)表示n的不同拆分的种数,例如f(7)=6. 要求编写程序,读入n(不超过1000000),输出f(n)%1000000000。

Examples:

Input:
每组输入包括一个整数:N(1<=N<=1000000)。
Output:
对于每组数据,输出f(n)%1000000000。

Solutions

  • 动态规划题目, 主要要能找到转移方程。
  • 具体看下面的代码

C++ Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
* 整数拆分
* 动态规划
* f(2m)=f(2m-1)+f(m)
* f(2m+1)=f(2m)
*/
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

#define ll long long
#define MAXN 1000000

ll N;
ll dp[MAXN+1];
memset(dp, 0, sizeof(dp));
dp[1]=1;
dp[2]=2;
for(ll i=3;i<=MAXN;i++){
if(i%2) dp[i]=dp[i-1]%1000000000;
else dp[i]=(dp[i-1]+dp[i/2])%1000000000;
}
while(cin>>N){
cout<<dp[N]<<endl;
}
return 0;
}