java - Java中的整数分区

Question

我正在尝试实现一个程序，该程序返回整数 n 的现有分区数作为分配的一部分。我写了下面的代码，但是它返回了错误的数字（Partitions n 返回了 Partitions n-1 的结果）。我不明白为什么会这样。我已经尝试了很多东西，但仍然不知道如何解决它，有人可以帮助我吗？

[edited code out to avoid plagiarism from my colleagues :p]

m 代表分区中允许的最大数，因此 partition(4,4) 将是 5 = 4, 3+1, 2+2, 2+1+1, 1+1+1+1，但是 partition (4 ,1) 将是 1 = 1+1+1+1。执行：java Partitions n

Answer 1

假设您正在调用partitions(4,4,memo). 正如您所说，答案应该是 5，因为有 5 种方法来划分整数：

4
3 + 1           <== counted by partition(1,3,memo)
2 + 2           <== counted by partition(2,2,memo)
2 + 1 + 1       <== counted by partition(2,2,memo)
1 + 1 + 1 + 1   <== counted by partition(3,1,memo)

所以看起来你的算法试图以上面显示的方式计算分区......但是你忘记计算一个分区了吗？