recursion - 找出一个数字可以写成两个或多个正数之和的方法数的算法

Question

这是一个家庭作业问题，必须使用动态编程方法来解决。

到目前为止，我设法做的是：

让 f(x) 表示 x 可以写的次数：

那么 f(x) = f(x - 1) + 1 ；f(5) = f(4) + 1 (5 = 4 + 1)

但我认为这不是正确的方法。有人愿意帮忙吗？

一个真正问题所在的例子：

4 的写法数：

4: 3 + 1
4: (2 + 1) + 1
4: 2 + 2
4: (1 + 1) + (1 + 1)

Answer 1

这种表示是 call partition。它可以通过不同的方式解决。

例如，假设

f(x, m) - number of partitions of x 
such that the largest number in that partition is m

然后

f(x, m) = sum of all f(x - m, k) where (1 <= k <= m),
also (k<=x-m), because f(x, y) = 0 where (y > x)

对于您的示例（让我们将数字本身也算作一个分区（f（x，x）= 1））

f(1, 1) = 1
f(2, 1) = f(1, 1) = 1
f(2, 2) = 1
f(3, 1) = f(2, 1) = 1
f(3, 2) = f(1, 1) = 1 //+ f(1, 2) zero
f(4, 1) = f(3, 1) = 1 
f(4, 2) = f(2, 1) + f(2, 2) = 2
f(4, 3) = f(1, 1) = 1 // + f(1, 2) + f(1, 3) zeroes
f(4, 4) = 1

所以 f(4, 1), f(4, 2), f(4, 3), f(4, 4) = 5 的总和（如果不计算 4，则 4 本身就是一个分区）