组合或其他方法？

Question

我最近读过这个问题,首先,我想到了一个组合方法,但似乎没有人 - 在参赛者中 - 提交了这样的解决方案.使用组合学的解决方案是否可行？如果没有,解决方案是什么？问题简单地说是:给定一个M字的字典,其中任何两个字可以连接在一起并且可能彼此重叠一些字母,找到可以从字典中形成多少长度为N的字符串.组合方法的下行限制为M!,然后对于每两个连续的单词,您应该尝试将它们相交.这就是我的想法.我怀疑它是否有效.请帮忙？

Answer 1

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

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

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

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

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