2

我在某处在线找到了这段代码，我试图弄清楚它是如何工作的。您为 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]
4

2 回答 2

1

这似乎是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 个不同部分）。

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

于 2020-06-25T05:22:47.133 回答
0

乍一看，它看起来像是按照“等分区子集和”的方式进行的记忆。

您可能从这里的答案中得到了代码： https ://leetcode.com/problems/partition-equal-subset-sum/

您可以在此处或此处找到有关其工作原理的说明： https ://www.education.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews/3jEPRo5PDvx

这里的一般想法是首先n询问“我如何n从以每种可能方式拆分的数字子集进行计算”？（拆分发生在递归调用处memo[h][l] = (bricks...）。每个递归都可以进一步拆分，以尝试形成与前一个拆分等剩余的任何差异。

注意：如果“h”和“l”分别是“高”和“低”，那么它们似乎是倒退的。

于 2020-06-25T04:08:41.163 回答