algorithm - (ProjectEuler) 求和组合

Question

来自 ProjectEuler.net :

问题 76:一百可以有多少种不同的写法作为至少两个正整数的和？

我不知道如何开始...有任何正确方向或帮助的要点吗？我不是在寻找如何去做，而是在寻找一些关于如何去做的提示。

例如5可以这样写:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

所以总共有 6 种可能性。

Answer 1

Partition Numbers (或分区函数)是这一个的关键。

如果您从底部开始逐步向上看是否可以检测到任何模式，那么此类问题通常会更容易。

• P(1) = 1 = { 1
• P(2) = 2 = {[2], [1 + 1]}
• P(3) = 3 = {[3], [2 + 1], [1 + 1 + 1]}
• P(4) = 5 = {[4], [3 + 1], [2 + 2], [2 + 1 + 1], [1 + 1 + 1 + 1]}
• P(5) = 7 ...
• P(6) = 11 ...
• P(7) = 15 ...
• P(8) = 22 ...
• P(9) = 30 ...

提示:看看您是否可以根据 P(N) 之前的结果的某种组合来构建 P(N)。