我看到了以下我无法解决的问题。什么样的算法会解决？
我们得到了一个正整数 n。令 A 为长度为 n 的所有可能字符串的集合，其中字符来自集合 {1,2,3,4,5,6}，即掷 n 次骰子的结果。 A 的多少个元素至少包含以下字符串之一作为子字符串:
1, 2, 3, 4, 5, 6
1, 1, 2, 2, 3, 3
4, 4, 5, 5, 6, 6
1, 1, 1, 2, 2, 2
3, 3, 3, 4, 4, 4
5, 5, 5, 6, 6, 6
1, 1, 1, 1, 1, 1
2, 2, 2, 2, 2, 2
3, 3, 3, 3, 3, 3
4, 4, 4, 4, 4, 4
5, 5, 5, 5, 5, 5
6, 6, 6, 6, 6, 6
我想知道某种递归方法，但当我尝试解决问题时却一团糟。
最佳答案
我建议阅读 Aho-Corasick algorithm .这构造了一个基于一组字符串的有限状态机。 (如果您的字符串列表是固定的，您甚至可以手动执行此操作。)
一旦你有了一个有限状态机(大约有 70 个状态)，你应该添加一个额外的吸收状态来标记何时检测到任何字符串。
现在您的问题简化为找出 6**n 串中有多少串在被推过状态机后最终处于吸收状态。
您可以通过将状态机表示为矩阵来做到这一点。条目 M[i,j] 表示添加一个字母后从状态 j 到达状态 i 的方法数。
最后，您计算矩阵的 n 次幂应用于输入向量，该向量除对应于初始状态的位置上的 1 外全为零。吸收状态位置的数字将告诉您字符串的总数。
(您可以使用标准 matrix exponentiation algorithm 在 O(logn) 时间内生成此答案。)
关于algorithm - 计算序列数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45263707/