完全背包问题

类似于”完全背包问题”, “商品”的体积分别为1, 2, 3, …, N, 个数不限.
属性从max改为个数.
注意, “至少拆分成 2 个数的和”, 因此, 最后必须将”只有1个数字之和”的方案排除掉.

时间复杂度

O(N^2)

Python 代码

"""
类似于"完全背包问题", "商品"的体积分别为1, 2, 3, ..., N, 个数不限.
属性从max改为个数.
注意, "至少拆分成 2 个数的和", 因此, 最后必须将"只有1个数字之和"的方案排除掉.

"""

MOD = 2147483648
N = int(input())
dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N + 1):
    for j in range(i, N + 1):
        dp[j] = (dp[j] + dp[j - i]) % MOD
print((dp[N] - 1) % MOD)