会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
本题要求统计所有“同源游走”的数量。游走本质上是从标牌序列中按原顺序选出的一个非空子序列，并且要求子序列的首尾房间标牌字母相同。
-
分类统计：
- 长度为 1 的游走：起点与终点是同一个房间，首尾字母天然相同，共有 n 条（其中 n 为字符串长度）。
- 长度大于等于 2 的游走：需要首尾字母相同，中间的房间可以任意选择参观或不参观。假设选择了位置 i 和 j 作为起止房间（i<j），且 s[i]=s[j]，则中间有 j−i−1 个房间，每个房间可选或不选，方案数为 2j−i−1。
-
优化计算：
