一、题目
1、原题链接
3382. 整数拆分
2、题目描述
一个整数总可以拆分为 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
二、解题报告
1、思路分析
我的思路
（1）想到了好像是完全背包问题，但是不会应用到题目中，所以直接暴力dfs了，只能过20%的数据。
（2）主要思路：先将不大于n的所有的2的次幂预处理出来，然后对这些数进行组合，每个数可以重复选，但是注意不要重复计算方案（每次从当前位置开始，选后面的数进行dfs即可避免，就是每次搜索只从当前数和其后面数开始搜索，不搜索其前面的数）。
y总思路
思路来源：y总讲解视频
y总yyds
（1）可以将该问题转化为类似完全背包问题。每个2的次幂为物品，其值为物品体积，而背包的容量为n。
（2）dp[i][j]表示从前i个物品中选总体积恰好为j的方案的总数。
（3）按照第i个物品选几个对dp[i][j]进行分类，则类似完全背包问题可以得到转移方程 dp[i][j]=dp[i-1][j]+dp[i][j-v[i]]。
（4）因为每次转移时只需要用到本层其左边和上一层当前位置的值，所以可以利用 滚动数组，从前小到达枚举背包体积进行空间优化：dp[j]=dp[j]+dp[j-v[i]]。
2、时间复杂度
我的思路时间复杂度O(nlogn+1)
y总思路时间复杂度O(nm)（n为物品数，m为背包体积）
3、代码详解
我的思路
#include <iostream>
using namespace std;
const int N=110,mod=1e9;
int v[N]; //记录每个2的次幂的值
int n,cnt,ans;
//搜索方案数，target为目标值，sum为当前已经搜索的数的总和，st为当前应该开始搜索的位置
void dfs(int target,int sum,int st){
//如果当前总和已经大于目标值，继续搜索一定找不到一组方案，直接回溯即可
if(sum>target) return ;
//如果当前总和正好等于目标值，说明是一种方案，使方案数+1，然后回溯
if(target==sum){
ans++;
return ;
}
//每次从当前位置（包括当前位置）向后搜索，注意剪枝：当前总和如果加上枚举的数之后已经大于target就没必要深搜了
for(int i=st;i<cnt&&sum+v[i]<=target;i++){
dfs(target,sum+v[i],i);
}
}
int main(){
cin>>n;
//预处理出每个2的次幂的值
for(int i=1;i<=n;i*=2) v[cnt++]=i;
dfs(n,0,0);
cout<<ans%mod;
return 0;
}
y总思路
#include <iostream>
using namespace std;
const int N=1000010,mod=1e9;
int dp[N];
int n;
int main(){
cin>>n;
dp[0]=1; //体积为0的方案数只有一种
for(int i=1;i<=n;i*=2){ //枚举物品
for(int j=i;j<=n;j++){ //枚举背包体积
dp[j]=(dp[j]+dp[j-i])%mod; //转移方程
}
}
cout<<dp[n];
return 0;
}
三、知识风暴
背包DP
0-1背包问题：参考我的这篇博客
完全背包问题
