动态规划问题：用c++实现将一个整数分解成若干个整数的和,且这些整数都是2的k次方(k>=0),问：有多少种解法?比如5=1+1+1+1+15=1+1+1+25=1+2+25=1+4有四种分解方法另附我的代码：#includeusingnamespacestd

Question

动态规划问题：用c++实现将一个整数分解成若干个整数的和,且这些整数都是2的k次方(k>=0),问：有多少种解法?
比如
5=1+1+1+1+1
5=1+1+1+2
5=1+2+2
5=1+4
有四种分解方法
另附我的代码：
#include
using namespace std;
int Array[21]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
_int64 Record[1000001][21]={0};
int partition(int n,int k)//n不超过2^k的分解
{
if(Record[n][k]!=0)
{
return Record[n][k];
}
else
{
if(n==1||k==0)
{
Record[n][k]=1;
return Record[n][k];
}
else if(n0)
{
while(n>Array[k]&&k

Answer 1

动态规划转移方程：
a[n] = a[n-1] ,n是奇数
a[n] = a[n-2] + a[n/2] ,n 是偶数
代码：
#include
using namespace std;
__int64 a[1000100];
int flag(0);
int main()
{
a[0] = 1;
a[1] = 1;
a[2] = 2;
while(cin>>n,n) //input integer n
{
for(int i=flag;i>1])%1000000000;
}
flag = n;
cout