第 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 上关注我或联系我
以上就是代码日亚麻布布局的出现的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2174859.html
