找不到.获得总和n的方法,其中所有正整数小于n

Question

对于给定的数字n,比如2,我们可以使用少于2的数字获得总和2的方式.

1+1 = 2  
so, for 2 - just 1 way.

n = 3   
1+1+1=3  
1+2=3  
so,for 3 - it is 2 ways  
n = 4   
1+1+1+1=4  
1+1+2=4  
1+3=4  
2+2=4  

so, for 4 - it is 4 ways  

这个问题可以有一个通用的模式/解决方案吗？

Answer 1

此问题称为分区问题,请参阅wiki引用的链接中的详细信息:

获得分区函数句柄的一种方法涉及中间函数p(k,n),其表示仅使用至少与k一样大的自然数的n的分区数.对于任何给定的k值,由p(k,n)计数的分区恰好符合以下类别之一:

smallest addend is k
smallest addend is strictly greater than k.

满足第一条件的分区数是p(k,n -k).为了看到这一点,想象一下将数字n-k的所有分区列表到大小至少为k的数字,然后想象将"+ k"附加到列表中的每个分区.现在它的清单是什么？作为旁注,可以使用它来根据中间函数为分区函数定义一种递归关系,即

1+ sum{k=1 to floor (1/2)n} p(k,n-k) = p(n),

满足第二条件的分区的数量是p(k + 1,n),因为至少包含k的部分的至少k的部分必须具有至少k + 1的所有部分.

由于这两个条件是互斥的,满足任一条件的分区数是p(k + 1,n)+ p(k,n -k).因此递归定义的函数是:

p(k, n) = 0 if k > n

p(k, n) = 1 if k = n

p(k, n) = p(k+1, n) + p(k, n ? k) otherwise.

实际上,您可以通过memoization计算所有值,以防止额外的递归调用.

编辑:在他的评论中提到unutbu,在计算结束时你应该减1来输出结果.即P直到最后一步的所有值都应该按维基建议计算,但是在输出结果之前的最后一步,你应该减去它1.