题解 - 自然数无序拆分

题目描述

美羊羊给喜羊羊和沸羊羊出了一道难题，说谁能先做出来，我就奖励给他我自己做的一样礼物。沸羊羊这下可乐了，于是马上答应立刻做出来，喜羊羊见状，当然也不甘示弱，向沸羊羊发起了挑战。
可是这道题目有一些难度，喜羊羊做了一会儿，见沸羊羊也十分头疼，于是就来请教你。
题目是这样的：
把自然数Ｎ（N<＝100）分解为若干个自然数之和，求出有几种情况。
如N＝5时，有7种情况
5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+2+2
5=1+4
5=2+3
5=5
怎么样？你要加油帮助喜羊羊哦！

输入
一个自然数N(N<＝100）
输出
无序拆分的种数。
样例输入 Copy
5
样例输出 Copy
7

题意

给定一个自然数n，将其拆分成n1 + n2 + n3 + … + nk，其中n1 <= n2 <= n3 <= … <= nk，这样称其为一种拆分方案，问一共有多少种方案

分析

本题可以等价为 把1,2,3, … n分别看做n个物体的体积，这n个物体均无使用次数限制，问恰好能装满总体积为n的背包的总方案数（即完全背包的变形）

朴素做法

思路

f[i][j]表示前 i 个整数（1,2…,i）恰好拼成 j 的方案数，则状态转移方程为：

// 选0个i，1个i，2个i，…全部加起来
f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] + ...;
// 将 j 变为 j - 1 得：
f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2 * i] + ...;

所以可化简为

f[i][j] = f[i - 1][j] + f[i][j - 1] 

初始状态

// 当都不选时，方案数是 1（即前 i 个物品都不选的情况也是一种方案），所以需要初始化为 1
for (int i = 0; i <= n; i ++) f[i][0] = 1;

朴素版代码

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int N = 100 + 10;int n;
LL f[N][N];int main(){ios::sync_with_stdio;cin.tie(0),cout.tie(0);cin >> n;for (int i = 0; i <= n; i ++) f[i][0] = 1; // 容量为0时，前 i 个物品全不选也是一种方案for (int i = 1; i <= n; i ++) {for (int j = 0; j <= n; j ++) {f[i][j] = f[i - 1][j];  // 特殊 f[0][0] = 1if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]);}}cout << f[n][n] << endl;return 0;
}

运行时间

所有测试点共9ms

优化做法

思路

for (int i = 1; i <= n; i ++) {for (int j = 0; j <= n; j ++) {f[i][j] = f[i - 1][j]; if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]);}
}

可以用滚动数组的思想将其转化为一维，即

for (int i = 1; i <= n; i ++) for (int j = i; j <= n; j ++) f[j] = (f[j] + f[j - i]) % mod;

同时将初始状态改为

f[0] = 1; // 容量为0时，前 i 个物品全不选也是一种方案

优化版代码

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int N = 100 + 10;int n;
LL f[N];int main(){ios::sync_with_stdio;cin.tie(0),cout.tie(0);cin >> n;f[0] = 1;for(int i = 1;i <= n;i++)for(int j = i;j <= n;j++)f[j] = f[j] + f[j - i];cout << f[n];return 0;
}

运行时间

所有测试点共9ms

由于本题数据量小，n最大只有100，故优化后时间变化不明显，但数据量很大时，会有很明显的优势