一个美丽的字符串是指字符串中不存在任意相邻的字符相同。比如abc,acba都是美丽的。 现在给你一个字符串，你要找到它有多少个非空子序列是美丽的字符串。 子序列是指删掉字符串若干个（零个）元素后，保持剩下元素相对位置不改变后得到的字符串。

这是一道比较经典的动态规划问题，可以用 dp[i][j] 表示在以第 i 个字符结尾的子序列中，最后两个字符是 j 的美丽子序列个数。状态转移方程为：

dp[i][j] = sum(dp[k][m]) (1 <= k <= i-2, m != j and m != s[i-1] and s[k] != s[i-1])

其中，sum 表示对所有满足条件的 k 和 m 的 dp[k][m] 求和。最终答案即为所有 dp[i][j] 的和。

时间复杂度为 O(n^3)，可以通过此题。

相关问题

酷酷和丁丁玩猜拳，两人都按照一定的规律出拳，我们用A,B,C分别表示石头，剪刀，布。比如酷酷出拳的规律是“ABBC”，即他按照“石头，剪刀，剪刀，布，石头，剪刀，剪刀，布，……” 的顺序不断出拳。 现在给出两个人的出拳规律，以及比赛的局数n，请你算出猜了n局之后，谁获胜？

根据题目描述，我们需要根据两个人的出拳规律和比赛局数，来判断谁获胜。我们可以先将两个人的出拳规律转化为一个循环周期，然后再根据比赛局数来计算每个人的胜利次数，最后比较胜利次数即可。

具体步骤如下：

1. 将两个人的出拳规律转化为一个循环周期，即将规律按照顺序不断重复，直到长度达到比赛局数n为止。

2. 根据循环周期和比赛局数，计算每个人的胜利次数。具体方法是，对于每一局比赛，分别比较两个人的出拳，根据石头剪刀布的规则判断胜负，并记录胜利次数。

3. 比较两个人的胜利次数，输出获胜者。

下面是Python代码实现：

def get_winner(a_pattern, b_pattern, n):
    # 将出拳规律转化为循环周期
    a_cycle = (a_pattern * (n // len(a_pattern) + 1))[:n]
    b_cycle = (b_pattern * (n // len(b_pattern) + 1))[:n]

    # 计算胜利次数
    a_win = 0
    b_win = 0
    for i in range(n):
        if a_cycle[i] == 'A' and b_cycle[i] == 'C':
            a_win += 1
        elif a_cycle[i] == 'B' and b_cycle[i] == 'A':
            a_win += 1
        elif a_cycle[i] == 'C' and b_cycle[i] == 'B':
            a_win += 1
        elif a_cycle[i] == b_cycle[i]:
            pass
        else:
            b_win += 1

    # 比较胜利次数，输出获胜者
    if a_win > b_win:
        return '酷酷'
    elif a_win < b_win:
        return '丁丁'
    else:
        return '平局'

使用样例：

winner = get_winner('ABBC', 'ACBA', 10)
print(winner)  # 输出：丁丁

Ignore invalid cache file C:\Users\IMS\.npminstall_tarball\manifests\9\7\0\97004ea3acba3c5a130ba2ad6c3949cf.json怎么解决

您好！对于解决此问题，您可以尝试以下几种方法：

1. 清除 npm 缓存：在命令行中运行以下命令，以清除 npm 缓存：

npm cache clean --force

然后重新运行您的操作，看看问题是否解决。

2. 删除无效的缓存文件：根据错误消息中提到的路径，手动删除无效的缓存文件。在您的情况下，可以尝试删除 `C:\Users\IMS\.npminstall_tarball\manifests\9\7\0\97004ea3acba3c5a130ba2ad6c3949cf.json` 这个文件。然后重新运行操作，看看问题是否解决。

3. 更新 npm：确保您正在使用最新版本的 npm。在命令行中运行以下命令来检查 npm 版本：

npm -v

如果您的 npm 版本过旧，可以使用以下命令更新 npm：

npm install -g npm

然后重新运行您的操作，看看问题是否解决。

希望这些方法能够帮助您解决问题！如果问题仍然存在，请提供更多详细信息，以便我能够更好地帮助您。