程序地带

算法题 整数划分(Python)


一个正整数nn可以表示成若干个正整数之和,形如:n=n1+n2+…+nk,其中n1≥n2≥…≥nk,k≥1。


我们将这样的一种表示称为正整数n的一种划分。


现在给定一个正整数n,请你求出n共有多少种不同的划分方法。


输入格式


共一行,包含一个整数n。


输出格式


共一行,包含一个整数,表示总划分数量。


由于答案可能很大,输出结果请对109+7取模。


数据范围


1≤n≤1000


输入样例:


5

输出样例:


7
代码

看作n个物品,的完全背包问题


n = int(input())
dp = [0]*(n+1)
dp[0] = 1
mod = int(1e9+7)
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])

 


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/blowfire123/article/details/112689383

随机推荐

写代码痴迷怎么办?

写代码痴迷怎么办?

前言当初年少懵懂,那年夏天填志愿选专业,父母听其他长辈说选择计算机专业好。从那以后,我的身上就有了计院深深的烙印。从寝室到机房,从机房到图书馆&...

公众号:Java后端 阅读(587)

1010 一元多项式求导 (25分)

1010一元多项式求导(25分)设计函数求一元多项式的导数。(注:x​n​​(n为整数)的一阶导数为nx​n−1​​。)输入格式:...

该博主已死于找bug 阅读(177)

100次随机1到100不重复

题目1随机100次  2随机的数字1到100之间newRandom().nextInt(100);3随机的100个数放到长度100的int数组里 考点:只能100次随机 随机出1到100...

Chenchen- 阅读(362)