题目解析 我们考虑使用动态规划来统计所有的以 a，c，g，o 结尾的子序列的数量。 令 A,C,G,OA, C, G, OA,C,G,O 分别表示 a，c，g，o 结尾的子序列的数量。 遍历字符串 SSS，对于字符串 SSS 中的每个字符 SiS_iSi ，若其为 a，则将 AAA 加一；若其为 b，则将 BBB 更新为 B+AB + AB+A； 若其为 c，则将 CCC 更新为 C+BC + BC+B； 若其为 d，则将 DDD 更新为 D+CD + CD+C； 若为其他字符，则不做任何处理。 最终 DDD 即为所求的答案。 AC代码

先看这题：P2646 数数zzy - 洛谷 | 计算机科学教育新生态 如果字符串出现了 y ，那么在它之前的 z 任意挑两个和这个 y 都可以组成一个 zzy 的子序列。 所以核心代码如下： 这题同理，只不过复杂一些。 我们先记录 a 的数量。 如果一个字符是 c，那么在它之前所有的 a 与这个 c 都能组成一个 ac 的子序列，记录下来。 如果一个字符是 g，那么在它之前所有的 ac 与这个 g 都能组成一个 acg 的子序列，记录下来。 如果一个字符是 o，那么在它之前所有的 acg 与这个 o 都能组成一个 acgo 的子序列，记录下来。 答案就出来了！ 时间复杂度：O(N)O(N)O(N)。