题目描述
一个正整数n可以表示成若干个正整数之和,形如:n=n1+n2+…+nk,其中n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数n的一种划分。
现在给定一个正整数n,请你求出n共有多少种不同的划分方法。
python 代码
"""
容量为n的背包,有n件物品
"""
n = int(input())
dp = [0]*(n+1) ##dp[i]表示背包容量为i时的方案数
dp[1] = 1
for i in range(1,n+1): ##可选数字范围
for j in range(i,n+1): ##背包容量
dp[j] = dp[j] + dp[j-i]
print(dp[n])