一尘不染

(ProjectEuler)总和组合

algorithm

ProjectEuler.net

问题76:至少有两个正整数之和,可以用多少种不同的方式写一百?

我不知道该如何开始…在正确的方向或帮助中有什么要点吗?我不是在寻找如何做,而是关于如何做的一些 提示

例如5可以写成:

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

因此共有6种可能性。


阅读 282

收藏
2020-07-28

共1个答案

一尘不染

分区号(或分区功能)是这一点的关键。

如果您从最底端开始并逐步向上看是否可以检测到任何模式,则此类问题通常会更容易。

  • 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)。

2020-07-28