A25682. 拆分正整数编程实现给定一个正整数 n，将 n 拆成一组各不相同的正整数，使得这组正整数的个数大于等于 2 且总和为 n。请计算有多少种不同的拆法；如果不能按要求拆分，输出 0。注意：几种拆法中，如果包含的整数完全相同，仅顺序不同，则视为同一种拆法。例如：{1, 2, 3}、{2, 1, 3} 和 {3, 2, 1} 被视为同一种拆法。例如：n = 6；满足要求的拆法有以下 3 种：第一种：{1,…
填空题
中等
知识点
题目描述
拆分正整数
编程实现
给定一个正整数 n，将 n 拆成一组各不相同的正整数，使得这组正整数的个数大于等于 2 且总和为 n。
请计算有多少种不同的拆法；如果不能按要求拆分，输出 0。
注意：几种拆法中，如果包含的整数完全相同，仅顺序不同，则视为同一种拆法。例如：{1, 2, 3}、{2, 1, 3} 和 {3, 2, 1} 被视为同一种拆法。
例如：n = 6；满足要求的拆法有以下 3 种：
第一种：{1, 5}；
第二种：{2, 4}；
第三种：{1, 2, 3}。
输入描述
输入一个正整数 n（1≤正整数≤90）。
输出描述
输出一个整数，表示有多少种拆法满足要求。
样例输入
6样例输出
3参考答案
def cal(n):
# dp[i] 表示将 i 拆分为若干不同的正整数的方式数
dp = [0] * (n + 1)
dp[0] = 1 # 拆分 0 的方式有 1 种
# 从 1 到 n，逐步加上每个数
for i in range(1, n + 1):
for j in range(n, i - 1, -1): # 倒序遍历，避免重复使用同一个数
dp[j] += dp[j - i]
# 返回 dp[n] 减去拆分 1 个数的情况（即 dp[n] - 1）
return dp[n] - 1
n = int(input())
print(cal(n))
上一题
下一题