algorithm - 组合学还是其他方法？

Question

我最近阅读了这个问题，首先，我想到了一种组合方法，但似乎没有人 - 以及参赛者 - 提交了这样的解决方案。使用组合数学的解决方案可能吗？如果不是，有什么解决办法？简而言之，问题是：给定一个包含 M 个单词的字典，其中任意两个单词可以连接在一起，并且可能会相互重叠一些字母，求从字典中可以形成多少个长度为 N 的字符串。组合方法的下限为 M!，那么对于每两个连续的单词，您应该尝试将它们相交。我就是这么想的。我怀疑它会起作用。请帮忙？

Answer 1

不要将组合学与蛮力混淆。这显然是一个组合计数问题，但时间限制也排除了任何蛮力解决方案。

我认为你可以通过动态编程来解决这个问题。例如，假设我们的子字符串是“CAT and TCAT”，我们需要覆盖一个大小为 100 的单词

如果我们以“CAT”开头，我们还剩下 97 个字母 如果我们以“TCAT”开头，我们还剩下 96 个字母。

因此，如果 f(n) 是大小为 n 的匹配的解数，我们将有 f(100) = f(97) + f(96)。

但是请注意，这显然过于简化且不够 - 您还需要涵盖字符串重叠的情况，并确保您不会两次计算相同的解决方案。

Answer 2

如果忽略重叠，这就是子集和问题。并考虑重叠，如果你用它们的连接替换重叠组合，你会得到一组没有重叠可能性的单词，然后如果你用它们的长度替换字符串然后想要找到加起来的总和到 N，这正是子集和问题。