python动态规划实现整数拆分_python将一个数拆成多个数的和,python整数拆分资源-CSDN下载

版权申诉

5星 · 超过95%的资源 194 浏览量 2021-01-20 02:18:42 上传评论 1 收藏 143KB PDF 举报

资源详情

资源评论

资源推荐

python 动态规划实现整数拆分动态规划实现整数拆分

我们先来看这样一个问题：

把5拆分成若干无序正整数的和（若干可以包含1），请问有多少种拆分方法？

直接用枚举法实现：

5 = 5

5 = 4+1

5 = 3+2

5 = 3+1+1

5 = 2+2+1

5 = 2+1+1+1

5 = 1+1+1+1+1

很显然，结果为7。注意这里5 = 4+1和5=1+4是相同的，只计算为一种方法。（如果计算为两种，那么属于有序拆分，实现起来较为容易，用排列组合中的插板法即可）

可以发现当待拆分数很小时，比较容易枚举出答案。

但是若要将10进行拆分，结果有42种；若要将20进行拆分，结果有627种；若要将30进行拆分，结果有5604种；若要将40进行拆分，结果有37338种···难度直线上升

网上搜索发现有很多种方法来解决这类问题，如递归，动态规划，母函数法，五边形法等等，本文只挑选较为容易理解的前两种来进行讨论。

一、递归法

用F（n）表示将n拆分的种数，如F（1）=1，F（2）=2，F（3）=3，F（4）=5，F（5）=7···F（10）=42···

用f(n,m)表示将n进行拆分，其中的最大拆分数不超过m，如

f(4,4) = F(4)

f(4,3) = 4 分别是(3+1),(2+2),(2+1+1),(1+1+1+1),但不包含(4)

f(5,2) = 3 分别是(2+2+1),(2+1+1+1),(1+1+1+1+1)

讨论f(n,m)函数的性质（摘录自百度百科）：

（1）当n=1时，不论m的值为多少（m>0），只有一种划分；

（2）当m=1时，不论n的值为多少（n>0），只有一种划分;

（3）当n=m时，根据划分中是否包含n，可以分为两种情况：

（a）划分中包含n的情况，只有一个，即(n)；

（b）划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有（n-1）划分；因此，f(n,n) = 1 + f(n, n – 1);

（4）当n<m时，由于划分中不可能出现负数，因此就相当于f(n,n)；

（5）当n>m时，根据划分中是否包含m，可以分为两种情况：

（a）划分中包含m的情况，即{m,{x1,x2,x3,…,xi}}，其中{x1,x2,x3,…,xi}的和为n-m，可能再次出现m，因此是（n-m）的m划分，因此这种划分个数为f(n-m,m)；

（b）划分中不包含m的情况，则划分中所有值都比m小，即n的（m-1）划分，个数为f(n,m-1)。因此，因此，f(n,m)=f(n-m,m)+f(n,m-1) 。

综上

def GetPartitionCount(n,m): #递归算法

if n == 1 or m == 1:

return 1

elif n < m:

return GetPartitionCount(n,n)

elif n == m:

return 1 + GetPartitionCount(n,n-1)

else:

return GetPartitionCount(n-m,m) + GetPartitionCount(n,m-1)

该算法的优点是代码简单明了，但是时间复杂度为O(2^n),计算F（100）需要几分钟！

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

评论2

刘明双

2023-04-19

非常有用的资源，有一定的参考价值，受益匪浅，值得下载。

内容反馈

版权申诉

weixin_38646634

粉丝: 4

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip