对于给定的数字 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
这个问题可以有一个通用的模式/解决方案吗?
最佳答案
此问题称为 Partition Problem ,请参阅来自 wiki 的引用链接中的详细信息:
One way of getting a handle on the partition function involves an intermediate function p(k, n), which represents the number of partitions of n using only natural numbers at least as large as k. For any given value of k, partitions counted by p(k, n) fit into exactly one of the following categories:
smallest addend is k smallest addend is strictly greater than k.
The number of partitions meeting the first condition is p(k, n − k). To see this, imagine a list of all the partitions of the number n − k into numbers of size at least k, then imagine appending "+ k" to each partition in the list. Now what is it a list of? As a side note, one can use this to define a sort of recursion relation for the partition function in term of the intermediate function, namely
1+ sum{k=1 to floor (1/2)n} p(k,n-k) = p(n),
The number of partitions meeting the second condition is p(k + 1, n) since a partition into parts of at least k that contains no parts of exactly k must have all parts at least k + 1.
Since the two conditions are mutually exclusive, the number of partitions meeting either condition is p(k + 1, n) + p(k, n − k). The recursively defined function is thus:
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 以输出结果。 IE。到最后一步的所有 P
值都应该按照 wiki 的建议进行计算,但是在输出结果之前的最后,你应该将它减去 1
.
关于algorithm - 找到没有。获得所有小于 n 的正整数的和 n 的方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8193438/