用f[n]
表示对n
的有效划分的方案数量,考虑状态转移时,我们考虑划分方案中最大的那个数。最大的那个数,可以是n
,n-1
,n-2
,.....,1
则我们更改一下状态表示,用f[n][m]
来表示,对n
的有效划分,且划分方案中最大的那个数不超过m
时,划分方案的个数。则最后的答案就是f[n][n]
我们的状态转移方程如下:
f[n][m] = f[n - m][m] + f[n - (m - 1)][m - 1] + f[n - (m - 2)][m - 2] + ..... + f[n - 1][1]
考虑另一个状态,f[n][m - 1]
,有
f[n][m - 1] = f[n - (m - 1)][m - 1] + f[n - (m - 2)][m - 2] + .... + f[n - 1][1]
进行替换,则有
f[n][m] = f[n - m][m] + f[n][m - 1]
注意,当n < m
时,有f[n][m] = f[n][n]
,因为对n
的划分,最大的那个数不可能超过n
接下来根据这个状态转移方程,我们列几个比较好计算的状态,来进行验证,并推出初始状态应该是怎么样的
f[1][1] = f[0][1] + f[1][0] = 1; // 对1的划分,最大的数不超过1,方案数明显是1
f[2][1] = f[1][1] + f[2][0] = 1; // 对2的划分,最大的数不超过1,方案数明显还是1
容易得知,对任意的 i >= 1,总是有f[i][1] = 1,因为最大的数不超过1,方案只可能是i个1相加
但我们不需要初始化全部的f[i][1] = 1,下面进行解释
容易得知,对于i >= 1,f[i][0]是始终为0的,因为最大的数不超过0,是不可能存在有效的划分方案的
但是有 f[1][1] = f[0][1] + f[1][0] = 1
f[1][0]明显是为0的,而f[0][1],由于0<1了,根据上面的描述,其实f[0][1] = f[0][0]
所以我们只需要初始化f[0][0] = 1
代码如下
#include <iostream>
using namespace std;
const int N = 1010, MOD = 1e9 + 7;
int f[N][N], n;
int main() {
cin >> n;
f[0][0] = 1; // 初始状态
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) { // j只枚举到i, 因为对于超过i的j,都可以看作f[i][j] = f[i][i]
if (i - j >= j) f[i][j] = (f[i][j - 1] + f[i - j][j]) % MOD;
else f[i][j] = (f[i][j - 1] + f[i - j][i - j]) % MOD; // 当 f[n][m] 中有 n < m 时, 直接当作 f[n][n] 来计算
}
}
cout << f[n][n] << endl;
return 0;
}