1.题目
一个整数总可以拆分为 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) 表示 nn 的不同拆分的种数，例如 f(7)=6。
要求编写程序，读入 n，输出 f(n)mod10的9次。
输入格式
一个整数 n。
输出格式
一个整数，表示 f(n)mod10的9次。
数据范围
1≤N≤106
输入样例：
9
输出样例：
6
2.思路
这个题目也可以用背包dp求，2的n次幂就是每一个物品，他本身的价值就是体积
不过不同的是这个集合属性求解的是次数
定义一个int [][]f=new int[20][N] 表示从前i个物品拿，且体积正好等于j的方案个数集合
对于第i个物品，可以拿 0个，也可以拿 k个
现在就可以套完全背包的模板了
3.Ac代码
import java.util.Scanner; public class Main { static int N=1000010,MOD = 1000000000; static int m; static int [][]f=new int[21][N]; //表示从前i个物品拿，且体积正好等于j的方案个数集合 public static void main(String[] args) { Scanner sc=new Scanner(System.in); m=sc.nextInt(); f[0][0]=1; //什么都不选也是一种方案 int n=0; //v就是每一个物品 ，j是体积 for (int i = 1,v=1; v <=m; v=v*2,i++) { n++; for(int j=0; j<=m; j++){ f[i][j]=f[i-1][j]; if(j>=v){ f[i][j]=(f[i][j]+f[i][j-v])%MOD; } } } System.out.println(f[n][m]); } }
4.优化
import java.util.Scanner; public class Main { static int N=1000010,MOD = 1000000000; static int n; static int []f=new int[N]; //表示从前i个物品拿重量正好等于j的方案个数集合 public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); f[0]=1; for (int i = 1; i <=n; i*=2) { for(int j=i ;j<=n; j++){ f[j]=(f[j]+f[j-i])%MOD; } } System.out.println(f[n]); } }
感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下
