整数拆分

#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
vector<int> v;
int dp[1000001];
const int mod=1000000000;
int main(){
	int i,j,N;
	for(i=0;i<=20;i++) v.push_back((int)pow(2,i));
	for(j=0;j<=1000000;j++) dp[j]=1;
	for(i=1;i<=20;i++)
		for(j=1;j<=1000000;j++)
			if(j>=v[i])
				dp[j]=(dp[j]+dp[j-v[i]])%mod;
	while(scanf("%d",&N)!=EOF)
		printf("%d\n",dp[N]);
}//背包问题  提前把表打好

#include <iostream>
using namespace std;
int main(){
   int a[21];
   a[0]=1; 
   for(int i=1;i<=20;i++)a[i]=a[i-1]*2;
   int b[1000001];
   b[0]=1;
   for(int i=0;i<=20;i++)
   {
       for(int j=a[i];j<=1000000;j++)
       {
         b[j]+=b[j-a[i]];
         if(b[j]>=1000000000)b[j]%=1000000000;
       }
   }
   int c=0; 
   while(cin>>c)cout<<b[c]<<endl;
   return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6;
long long dp[maxn+5];
int n;

void getDP()
{
    dp[0] = 1;
    for(int i = 1;i <= maxn; i++)
    {
        if(i & 1) dp[i] = dp[i-1] % 1000000000;
        else dp[i] = (dp[i-1]+dp[i/2]) % 1000000000;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    getDP();
    while(cin >> n)
    {
        cout << dp[n] << '\n';
    }
    return 0;
}

//递推公式 n=1时 1种方式 n=2时(f[n]=2)2种方式 n=3时 2种方式 n=4时4种方式
//   n为奇数是f[n]=f[n-1]   n为偶数时f[n]=f[n-1]+f[n/2]
#include<stdio.h>
int main()
{//实际上在自己本地编辑器里面f[1000000]会出现错误,[]太大了,但是提交是没有问题的
    int n,i;
    int f[1000000];//n实际做f的下标,数组值作为方法个数
    scanf("%d",&n);
    f[1]=1;//n=1时只有一种方式
    for(i=2;i<=n;i++)//f的下标
    {
        if(i%2==0)//偶数
            f[i]=(f[i/2]+f[i-1])%1000000000;
        else//奇数
            f[i]=f[i-1]%1000000000;
    }
    printf("%d",f[n]);
    return 0;
}

#include <iostream>
#define MAXSIZE 1000001
using namespace std;

int get_num_of_div(int n){ //复杂度过高不通过
    if(n==1)
        return 1;
    if(n%2!=0)
        return get_num_of_div(n-1);
    else 
        return get_num_of_div(n-1)+get_num_of_div(n/2);
}

void init(int div[]){

}

int main(){
    int div[MAXSIZE];//辅助数组减轻时间复杂度。以后递推关系要么递归要么用数组把所有可能都算出来先
    int n;
    div[0]=div[1]=1;
    for(int i=2;i<MAXSIZE;i++){
        if(i%2==0)
            div[i]=(div[i-1]+div[i/2])%1000000000;
        else
            div[i]=div[i-1];
    }
    while(cin>>n){
        cout << div[n] << endl;
    }
}

把百度到的思路整理一下~
1.对于给定的整数，可以分奇偶讨论：
①N为奇，每个划分必含有1。
②N为偶，划分分为两类：S=A并B。其中任意a属于A，a含1；任意b属于B，b不含1。
2.设Sn为输入为n时的划分的全集，|Sn|表示划分的个数，则
①n为奇，Sn每个划分去掉1可以得到Sn-1，即|Sn-1|=|Sn|。
②n为偶，A每个划分去掉1可以得到Sn-1，即|A|=|Sn-1|；
         B每个划分除以2可以得到Sn/2，即|B|=|Sn/2|。
③S1=1.
有上面讨论可得程序：

python

这是动态规则的题目，关键是找到转移方程。

num = int(input())
dp = [1 for i in range(num + 1)]
for i in range(1, num + 1):
    if i % 2 == 1:
        dp[i] = dp[i - 1]
    else:
        dp[i] = dp[i - 1] + dp[i // 2]
print(dp[-1] % 1000000000)

//用的动态规划来做
#include<stdio.h>
int f[1000001];//主函数中的数组最大分配52万，所以放到全局作用域
int main(){
    int i,N;
    f[0]=f[1]=1;
    for(i=2;i<=1000000;i++){
        if(i%2)f[i]=f[i-1];//i为奇数
        else f[i]=(f[i-1]+f[i/2])%1000000000;//i为偶数
    }
    while(scanf("%d",&N)!=EOF)
        printf("%d\n",f[N]);
    return 0;
}

	

搬运一下思路：
记f(n)为n的划分数，我们有递推公式：

	f(2m + 1) = f(2m)，
f(2m) = f(2m - 1) + f(m)，
初始条件：f(1) = 1。



	证明:



	证明的要点是考虑划分中是否有1。



	记:
A(n) = n的所有划分组成的集合，
B(n) = n的所有含有1的划分组成的集合，
C(n) = n的所有不含1的划分组成的集合，
则有: A(n) = B(n)∪C(n)。



	又记:
f(n) = A(n)中元素的个数，
g(n) = B(n)中元素的个数，
h(n) = C(n)中元素的个数，
易知: f(n) = g(n) + h(n)。



	以上记号的具体例子见文末。



	我们先来证明: f(2m + 1) = f(2m)，
首先，2m + 1 的每个划分中至少有一个1，去掉这个1，就得到 2m 的一个划分，故 f(2m + 1)≤f(2m)。
其次，2m 的每个划分加上个1，就构成了 2m + 1 的一个划分，故 f(2m)≤f(2m + 1)。
综上，f(2m + 1) = f(2m)。



	接着我们要证明: f(2m) = f(2m - 1) + f(m)，
把 B(2m) 中的划分中的1去掉一个，就得到 A(2m - 1) 中的一个划分，故 g(2m)≤f(2m - 1)。
把 A(2m - 1) 中的划分加上一个1，就得到 B(2m) 中的一个划分，故 f(2m - 1)≤g(2m)。
综上，g(2m) = f(2m - 1)。



	把 C(2m) 中的划分的元素都除以2，就得到 A(m) 中的一个划分，故 h(2m)≤f(m)。
把 A(m) 中的划分的元素都乘2，就得到 C(2m) 中的一个划分，故 f(m)≤h(2m)。
综上，h(2m) = f(m)。



	所以: f(2m) = g(2m) + h(2m) = f(2m - 1) + f(m)。                                            



	这就证明了我们的递推公式。

#include<iostream>
#define MAXSIZE 1000001
using namespace std;


int main(){
	int n;
	int result[MAXSIZE];
	result[0] = result[1] = 1;
	for(int i = 2; i<MAXSIZE; ++i){
		if(i%2 == 0){
			result[i] = (result[i-1] + result[i/2])%1000000000;
		}
		else{
			result[i] = result[i-1]%1000000000;
		}
	}
	while(scanf("%d",&n) != EOF)
		cout<<result[n]<<endl;
	return 0;
}

/*这道题确实可以用动态规划来解,它其实是一个完全背包求恰装满背包时的方案总数
问题.具体是,因为每一个拆分必须是1,2,4,2^3,...2^19(考虑n最大为10^6),
所以对于一个整数n,看它的这种拆分数有多少个,就相当于现在有20种物品,第i种物品
的花费是2^(i-1),每一种可以重复取, dp[i][j]表示前i种物品恰装满容量为j的物品时
的方案总数,从而dp[i][j] = dp[i-1][j] + dp[i][j-a[i]]
*/     
#include <iostream>
#include <string>
#include <vector>
#include <map>

#include <queue>
#include <stack>
#include <algorithm>


#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>      //rand ( ), srand ( )
#include <ctime>        //time ( )
using namespace std;

int n, dp[1000002], a[21];

int main ( )
{
    int i, j, t;
    for ( i = 1; i <= 20; i ++ )
        a[i] = ( 1 << ( i - 1) );
    dp[0] = 1;
    while ( cin >> n )
    {
        memset ( dp + 1, 0, sizeof ( dp ) );
        for ( i = 1; i <= 20; i ++ )
        {
            for ( j = a[i]; j <= n; j ++ )
            {
                dp[j] += dp[j - a[i]];
                dp[j] %= 1000000000;
            }
        }
        cout << dp[n] << endl;
    }
    return 0;
}

	

#include<iostream>
using namespace std;
int dp[1000001];
long f2n(long n)
{
 for(long i=1;i<=n;i++)
 { 
   if(i==1)dp[i]=1;
      else if(i%2)dp[i]=dp[i-1];
        else dp[i]=(dp[i-1]+dp[i/2])%1000000000;
 }
 return dp[n];
}

int main()
{
    int n;
    while(cin>>n){
        cout<<f2n(n)<<endl;
    }
    return 0;
}

#include<iostream>
using namespace std;
int dp[1000001];
long f2n(long n)
{
 for(long i=1;i<=n;i++)
 { 
   if(i==1)dp[i]=1;
      else if(i%2)dp[i]=dp[i-1];
        else dp[i]=(dp[i-1]+dp[i/2])%1000000000;
 }
 return dp[n];
}

int main()
{
    int n;
    while(cin>>n){
        cout<<f2n(n)<<endl;
    }
    return 0;
}

dp[i]表示f(i)
状态转移方程
i是奇数：dp[i]=dp[i-1]
i是偶数：dp[i]=dp[i-1]+dp[i/2] 其中dp[i-1]表示拆分有1的种数，dp[i/2]表示拆分没有1的种数

#include <iostream>
#include <vector>
using namespace std;

/*
思路：
1、奇数：f(5)的分解方法为f(4) + 1，1不可再分，f(n) = f(n - 1)
2、偶数：f(4)的分解方法为2 + 1 + 1或2 + 2, f(n) = f(n - 2) + f(n / 2)
*/

int main() {
    long long n;
    while (cin >> n) {
        vector<long long> nums(n + 1);
        nums[1] = 1;
        nums[2] = 2;

        for (int i = 3; i <= n; i++) {
            if (i % 2 == 1) {
                nums[i] = nums[i - 1] % 1000000000;
            }
            else {
                nums[i] = (nums[i - 2] + nums[i / 2]) % 1000000000;
            }
        }

        cout << nums[n] << endl;
    }
    return 0;
}

#include<iostream>
using namespace std;
int f(int n)//递推关系,递归实现复杂度太高
{
    if(n == 1)
        return 1;
    if(n % 2 == 1)
        return f(n - 1);
    else
        return f(n - 1) + f( n / 2);
}
int ff(int n)
{
    int *array = new int[n+1];
    array[1] = 1;
    array[2] = 2;
    for(int i = 3; i <= n; i++)
    {
        if(i % 2 == 1)
            array[i] = array[i-1] % 1000000000;
        else
            array[i] = (array[i-1] + array[i/2]) % 1000000000;
    }
    return array[n];
}

int main()
{
    int num;
    cin >> num;
    cout << ff(num) << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int>dp(n + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 0)
                dp[i] = (dp[i - 1] + dp[i / 2]) % 1000000000;
            else
                dp[i] = dp[i - 1] % 1000000000;
        }
        cout << dp[n] << endl;
    }
    return 0;
}

有两种情况

1. n是奇数，必定可以拆出一个1，不管其他的部分怎么变，这个1不会改变，也就是说这个1不会影响拆分的结果，即

    dp[i]=dp[i-1]

2. n是偶数，拆分的结果只有两种情况，要么带有1的形式，要么不带1的形式（全是偶数）

   • 奇拆分（带有1的形式）：dp[i-1] 原因同上

   • 偶拆分（全是偶数的形式）：dp[i/2]

     dp[8] 4+4 2+2+4 2+2+2+2

     dp[4] 2+2 1+1+2 1+1+1+1

     可以发现dp[8]的偶拆分刚好是dp[4]所有拆分情况的2倍形式

     import java.io.BufferedReader;
     import java.io.IOException;
     import java.io.InputStreamReader;
     
     public class Main {
         public static void main(String[] args) throws IOException {
             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             String s;
             int[] dp = new int[1000001];
             dp[1] = 1;
             for (int i = 2; i <= 1000000; i++) {
                 if (i % 2 == 0) {
                     dp[i] = (dp[i / 2] + dp[i - 1]) % 1000000000;
                 } else {
                     dp[i] = dp[i - 1];
                 }
             }
             while ((s = br.readLine()) != null) {
                 int n = Integer.parseInt(s);
                 System.out.println(dp[n]);
             }
         }
     
     }