一、题目

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)mod10⁹。

输入格式

一个整数 n。

输出格式

一个整数，表示 f(n)mod10⁹。

数据范围

1≤N≤10⁶

输入样例：

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(n^logn+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背包问题：参考我的这篇博客
• 完全背包问题