把red换成123 dp[i][j]表示第i位为j时，从0-i达到满足要求需要的最小操作次数 则若原始串第i个位置为h， dp[i][j] = min(dp[i-1][k] * (k!=j) + trans(h,j)) 即前一个位置和j不相等的方案数+当前字符转换到j所需要的次数取最小值。 第四题 先打表找规律， 1:1 2:2 3:[1,2],[2,1],[3] 4:[1,2,1],[4] 5:[1,4],[2,1,2],[2,3],[3,2],[4,1],[5] 可以看到，第i个数的方案等于用1去和i-1的方案中以偶数开头的方案去组合，用2和i-2的奇数方案组合，以此类推，直到本身和0组合得到本身。 这样我们可以把每个数的方案数按照奇偶数开头分别存储，则有 odd[i] = even[i-1] + even[i-3] + ... even[i] = odd[i-2] + odd[i-4] + ... 再按照i的奇偶加到对应的位置上，可以看到是可以通过前缀和来优化到O(N)递推的，然后因为判断i的奇偶这里，导致我没够造出来对应的矩阵去做矩阵快速幂....