整数拆分
一个整数总可以拆分为 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的幂，然后有多少种选择的问题。
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]); } }
