AcWing 900. 整数划分
原题链接
简单
作者:
Scat
,
2024-04-12 15:18:25
,
所有人可见
,
阅读 1
完全背包方案
f[i][j]表示前i个数中,体积恰好为j的选法
为什么完全背包可以保证没有重复的方案的?
例如2, 1, 1和1, 2, 1 是一组相同方案,由于在状态转移时,我们都是考虑第i个数选几个是一个方案,所以在这里例子里,1选2个、2选1个是一个方案,而不会产生两个相同的方案
n = int(input())
f = [[0 for i in range(n + 1)] for i in range(n + 1)]
mod = 10 ** 9 + 7
f[0][0] = 1
for i in range(1, n + 1):
for j in range(n + 1):
f[i][j] = f[i - 1][j]
if j >= i:
f[i][j] = (f[i][j] + f[i][j - i]) % mod
print(f[n][n])
判断组成的数中最小值是否为1的方案
f[i][j]表示体积为i,由j个数组成的选法
n = int(input())
f = [[0 for i in range(n + 1)] for i in range(n + 1)]
mod = 10 ** 9 + 7
f[0][0] = 1
for i in range(1, n + 1):
for j in range(1, n + 1):
f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod
res = 0
for i in range(1, n + 1):
res =( res + f[n][i]) % mod
print(res)