整数拆分(c++,java)

一时失言乱红尘 2024-03-25 20:38 86阅读 0赞

## 整数拆分 ##

一个整数总可以拆分为 2 的幂的和。

例如：7可以拆分成

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

共计 6 种不同拆分方式。

再比如：4 可以拆分成：4=4,4=1+1+1+1,4=2+2,4=1+1+2。

用 f(n) 表示 n 的不同拆分的种数，例如 f(7)=6。

要求编写程序，读入 n，输出 f(n)mod109。

输入格式一个整数 n。

输出格式一个整数，表示 f(n)mod109。

数据范围  
1≤N≤106  
输入样例：  
7  
输出样例：  
6

### 提交代码 ###

**算法思路**  
这个题本质是一个dp问题，也就是现在又无数的物品，这些物品是2的幂，然后有多少种选择的问题。  
![在这里插入图片描述][4c7cb909981d48bcb5299a7fefdf091e.png]

**c++**

#include<iostream>
    using namespace std;
    
    const int N = 1e6 + 10;
    const int MOD = 1e9;
    
    int a[N];
    int n, f[N];
    
    int main()
    {
        
        cin >> n; 
        f[0] = 1; // 默认0的时候也有一种
        for (int i = 1; i <= n; i *= 2)  // 枚举2的幂 
        {
        
            for (int j = i; j <= n; ++ j) // 
            {
        
                f[j] = (f[j] + f[j - i]) % MOD;
            }
        }
        cout << f[n];
        return 0;
    }

**java**

import java.util.*;
    public class Main
    {
        
        static int N = 1000010, n, mod=(int)1e9;
        static int [] f = new int[N];
        static int [] w = new int[21]; // 一共有2^0~2^19二十种选法
        
        public static void main(String [] args)
        {
        
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            f[0] = 1;
            for(int i = 1; i <= 20; ++ i) w[i] = (int)Math.pow(2, i - 1);
            for (int i = 1; i <= 20; ++ i)
            {
        
                for (int j = w[i]; j <= n; ++ j) f[j] = (f[j] + f[j - w[i]]) % mod;
            }
            System.out.println(f[n]);
        }
    }

[4c7cb909981d48bcb5299a7fefdf091e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/127866b93de34b05bd5bc706dfc2f790.png