组合学或其他方法?

发布于 2024-11-18 05:09:45 字数 1459 浏览 4 评论 0原文

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

梦幻之岛 2024-11-25 05:09:45

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

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

,那么我们还剩下 97 个字母
如果我们以“TCAT”开头,我们还剩下 96 个字母。

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

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

Don't confuse combinatorics with brute force. This is clearly a combinatorial counting problem but the time limit also rules out any brute force solution.

I think you can solve this with dinamic programming. For example, suppose our substring are "CAT and TCAT" and we need to cover a word of size 100

if we start with "CAT" we have 97 letters left
if we start with "TCAT" we have 96 letters left.

So, if f(n) is the number of solutions for a matching of size n, we would have f(100) = f(97) + f(96).

Note, however, that this is clearly too simplified and not enough - you also need to cover the cases where the strings overlap and make sure that you don't count the same solution twice.

与君绝 2024-11-25 05:09:45

如果忽略重叠,这就是子集和问题。考虑到重叠,如果您用它们的串联替换重叠组合,您将得到一组不可能重叠的单词,之后如果您用字符串的长度替换字符串,然后想要找到相加的总和到 N,这正是子集和问题。

if you ignore the overlap, this is the subset sum problem. and considering the overlap, if you replace the overlapping combinations with their concatenations, you'll get a set of words that have no possiblity of overlap, and after that if you replace the strings with their lengths and then want to find sums that add up to N, that is exactly the subset sum problem.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文