leetcode-2645 构造有效字符串的最小插入数

题目链接

2645. 构造有效字符串的最少插入数 - 力扣（LeetCode）

解题思路 动态规划

1、定义状态d[i]为将前i个字符（为了方便编码，下标从1开始）拼凑成若干个abc所需要的最小插入数。那么初始状态d[0]=0，最终要求解d[n]，其中n为word的长度。

2、转移过程

1、d[i] = d[i-1] + 2 当word[i]单独存在于一组abc中
2、d[i] = d[i-1] - 1 当word[i] > word[i-1],那么word[i]与word[i-1]存在同一组abc中

3、因为每个字符都尽可能与前面字符组合所以情况2优于情况1

代码

class Solution:
    def addMinimum(self, word: str) -> int:
        n = len(word)
        d = [0] * (n + 1)
        for i in range(1,n+1):
            d[i] = d[i - 1] + 2
            if i > 1 and word[i-1] > word[i - 2]:
                d[i] = d[i -1] - 1
        return d[n]