时间戳

首页 > 解决方案 > 整数的不同分区，不包括重复组合

python - 整数的不同分区，不包括重复组合

问题描述

我在某处在线找到了这段代码，我试图弄清楚它是如何工作的。您为 partitions() 函数提供一个整数，代码返回不包括重复数字的不同分区的数量（例如 n = 5 -> 2 个分区 (3,2) & (4,1)）。我想了解这个递归解决方案究竟是如何管理这个的。我一直在玩弄代码，跟踪递归调用，但我仍然不太明白它是如何工作的。请帮我理解。

def partitions(n):
    memo = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
    return bricks(1, n, memo) - 1

def bricks(h, l, memo):
    if memo[h][l] != 0:
        return memo[h][l]
    if l == 0:
        return 1
    if l < h:
        return 0

    memo[h][l] = (bricks(h + 1, l - h, memo)) + (bricks(h + 1, l, memo))
 
    return memo[h][l]

标签： pythonrecursiondynamic-programminginteger-partition

解决方案

这似乎是OEIS A111133，划分n为至少 2 个不同部分的数量。

忘记所有琐碎的东西memo- 这只是一种优化，并掩盖了意图。剩下的变量名很糟糕。我将使用LandH代替（至少L不会 - 像l- 容易与数字 1 混淆）。

bricks(H, L)似乎是 L 分成不同部分的数量，其中最少的部分至少是 H。其中有多少？那么，H是在这样一个分区，或者它不是。如果H是，则L-H仍然存在，并且需要将其划分为最少的部分，其中至少是H+1。如果H不在这样的分区中，则L保留，并且需要将其分成最少的部分，其中最少为H+1. 将这些相互排斥的情况加在一起：

bricks(H, L) = bricks(H+1, L-H) + bricks(H+1, L)

如果L < H，则没有L至少有一个部分的分区H，所以为 0。由于bricks(L, L)必须为 1（显然有 1 个至少有一个部分的分区L）L，因此需要bricks(H, 0)返回 1 才能计算出上述总和。

最后，n分成至少 2 个不同部分的分区数是分成n至少1 个不同部分的分区数bricks(1, n)- 减去单例分区{n}（该分区没有至少 2 个不同部分）。

理解这里的障碍并不是代码本身——而是找出代码背后的想法。

推荐阅读