建个企业网站要多少钱,深圳品牌整合营销,免费网站建站2773,宁波智能模板建站题目链接
2645. 构造有效字符串的最少插入数 - 力扣#xff08;LeetCode#xff09;
解题思路 动态规划
1、定义状态d[i]为将前i个字符#xff08;为了方便编码#xff0c;下标从1开始#xff09;拼凑成若干个abc所需要的最小插入数。那么初始状态d[0]0#xff0c;最终…题目链接
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,n1):d[i] d[i - 1] 2if i 1 and word[i-1] word[i - 2]:d[i] d[i -1] - 1return d[n]
