整数拆分

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[]b = new int[n+1];
        int[]a = new int[n+1];
        int x = 0;
        for(int i = 0;i<=n;i++){
            b[i] = (int)Math.pow(2.0,i);
            if(b[i]>n){
                x = i;
                break;
            }
        }
        a[0] = 1;
        for(int i = 0;i<x;i++){
            for(int j = b[i];j<=n;j++){
                a[j]+=(a[j-b[i]]%1000000000);
                a[j]%=1000000000;
            }
        }
        System.out.println(a[n]);
    }
}

有两种情况

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]);
             }
         }
     
     }
     
     

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int[] dp = new int[1000001];
        dp[0]=1;
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();

            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;
                }
            }
            System.out.println(dp[n]);;
        }
    }
}