构造回文的最小插入次数 :: labuladong的算法小抄

[labuladong]

文章链接点这里：构造回文的最小插入次数

[Dereshi]

直接利用最长回文子序列就行。。除去最长子序列，剩下的每个char需要insert一个新的char与其对称

[Nelsonlin0321]

class Solution:
    def minInsertions(self, s: str) -> int:
        
        row = [0 for _ in range(len(s))]
        dp = [row.copy() for _ in range(len(s))]
        
        # base case
        
        for i in range(len(s)):
            dp[i][i] = 0
        
        
        for i in range(len(s)-1,-1,-1): # start
            for j in range(i+1,len(s)): # end
                
                if s[i]==s[j]:
                    dp[i][j] = dp[i+1][j-1]
                else:
                    dp[i][j] = min(dp[i+1][j],dp[i][j-1]) + 1
        
        return dp[0][-1]

[zhongweiLeex]

又因为状态转移方程中 dp[i][j] 和 dp[i+1][j]，dp[i]-1]，dp[i+1][j-1] 三个状态有关，为了保证每次计算 dp[i][j] 时，这三个状态都已经被计算，我们一般选择从下向上，从左到右遍历 dp 数组

二、代码实现 这一段的 第二张图上面这段文字中， dp[i][j-1] 没写完整 ，写成了 dp[i]-1]

东哥，关注修改一下小小瑕疵哦。：>

[labuladong]

@zhongweiLeex 你看的好仔细啊，印象中你提了好几个错误😂，已修复

[zhongweiLeex]

@zhongweiLeex 你看的好仔细啊，印象中你提了好几个错误😂，已修复

哈哈哈 多谢东哥夸奖，这样比较有参与感和成就感 😄 , 感谢东哥的开源精神，让我们能得到这么好的刷题讲解！