代码日亚麻布布局的出现

第 19 天：亚麻布布局

GitHub 解决方案

今天的挑战与通常的 2D 谜题和 Dijkstra 算法相比有令人耳目一新的变化。以下是我的处理方法：

第 1 部分

目标很简单：检查是否可以使用可用的毛巾创建给定的毛巾布置。

不应该做什么：

最初，我尝试使用 itertools.combinations 生成所有可能的毛巾组合。很快我们就发现这既不实用也不高效。

什么有效：

使用递归结合字典（备忘录）来缓存已经处理过的设计。这可以防止冗余计算并使解决方案更加高效。

工作原理：

对于每个设计，尝试将开头与其中一种毛巾图案相匹配。
如果存在匹配，则删除匹配的部分并对剩余部分进行递归。
使用备忘录缓存我们已经检查过的设计结果，避免重复工作。
具有记忆功能的递归方法使复杂性保持可控，即使对于较大的输入也是如此，并使解决方案高效运行。

第二部分
第二部分提高了赌注：计算使用可用图案制作每条毛巾设计的方法数。

关键见解：
count_arrangements 函数扩展了第 1 部分中的递归逻辑，但现在计算构建设计的所有可能方法。

对于每条匹配的毛巾，递归设计的其余部分。
使用另一个字典（memo_count）来缓存之前解决的子问题的结果。

示例：
如果“brgr”可以通过两种方式构造，我们只需从缓存中返回 2，而不是重新计算它。

优化：
感谢第 1 部分，我们已经知道哪些设计是可能的。我们只计算这些的安排。

for arrangement in arrangements:
    if arrangement in memo and memo[arrangement]:
        ways = count_arrangements(arrangement, towels, memo_count)
        total_arrangements += ways

通过总结所有有效的方法，我们得到了第二部分的最终答案，就这么简单。

就像我说的，我发现今天的挑战很有趣，是一个很好的改变。我希望这篇文章对未来的挑战/编码有所帮助。

一如既往，请随时在 Twitter 上关注我或联系我

以上是代码日亚麻布布局的出现的详细内容。更多信息请关注PHP中文网其他相关文章！