algorithm - 计算将数字分成 4 部分的方法数

Question

给定一个正整数 n，找出将 n 分成四份或将 n 表示为四个正整数之和的方法数。这里的 n 从 0 到 5000 不等。

def foo(target, k, j):
    count = 0
    map = {} 
    if target in map.keys() and map[target] == k:
        return map[target]
    if target == 0 and k == 0:
        return 1
    if target <= 0 or k < 0:
        return 0
    for i in range(j, target+1):
        count += foo(target-i, k-1, i)
    map[target] = count
    return count

print(foo(10, 4, 1))

我已经用上面的递归解决方案解决了这个问题，但我只是看到有人用下面的动态规划解决方案。

f(0,0) = 1

f(target, k) = 0 如果 k > target 或 (target > 0 and k = 0)

f(目标, k) = f(目标-k, k) + f(目标-1, k-1)

有人可以启发我这个解决方案吗？

Answer 1

这个解决方案是正确的，但有点棘手，我会尽力向您解释清楚。

如果target=25，我们将其拆分为25=9+7+5+4。我们用4列(1*9、1*7、1*5、1*4)表示:

但换个角度看，你可以把图像看成9行(1*4, 1*4, 1*4 , 1*4, 1*3, 1*2, 1*2, 1*1, 1 *1).

因此，您会发现您的解决方案是按列构建图像，而该解决方案是按行构建图像。

因此我们来了解该解决方案的详细信息:

• f(目标, k) = f(目标-k, k) + f(目标-1, k-1)
• f(target, k):保留target 个方 block ，行的长度为k
• f(target - k, k): 放一行长度k
• f(target - 1, k - 1):只将一个方 block 放在最右边的列(确保答案是正整数)，并将行的长度减少 1。

就这些。

如果您还有任何问题，可以在这里发表评论。