algorithm - 找到号码。获得所有小于 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直到最后一步的所有值都应该按照wiki的建议计算，但是在最后输出结果之前，你应该减去它1。