# -*- coding: utf-8 -*-  class Solution:     """     题目：         https://www.nowcoder.com/practice/bae2652b4db04a438368238498e4c13e?tpId=196&tqId=40507&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=     参考：         https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/solution/rang-zi-fu-chuan-cheng-wei-hui-wen-chuan-de-zui--2/     算法：         题目要求计算让字符串成为回文串的最少插入次数。我们可以换个思路，如果我们知道字符串s中最长回文子序列，长度为m，那么剩余的字符就是破坏字符串s成为回文串的字符，我们只需要在对应位置添加n - m个字符就可以使s成为回文串。         比如：             字符串长度为偶数：s = "ab", n = 2, m = 1, 需要添加的字符数为n - m = 1，"ab" -> "aba" 或者 "bab"             字符串长度为奇数，s = "abc", n = 3, m = 1，需要添加的字符数为n - m = 3 - 1 = 2，"abc" -> "cbabc"         因此本题的关键在于，计算字符串s的最长回文子序列。而字符串s的最长回文子序列问题又可以转换为字符串s 与 其翻转字符串t = s[::-1]的最长公共子序列。         设dp[i][j]表示字符串s的前i个字符与字符串t的前j个字符的最长公共子序列。         边界条件：             dp[0][0] = 0             dp[0][j] = 0             dp[i][0] = 0         状态转移方程：             如果s[i - 1] == t[j - 1]：                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + 1)             否则：                  dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])     复杂度：         时间复杂度：O(n^2), n为字符串s的长度         空间复杂度：O(n^2)，辅助空间dp     """      def minInsert(self, str):         # write code here         t, n = str[::-1], len(str)          dp = [[0] * (n + 1) for _ in range(n + 1)]         maxLen = 0         for i in range(1, n + 1):             for j in range(1, n + 1):                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])                 if str[i - 1] == t[j - 1]:                     dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)                 maxLen = max(maxLen, dp[i][j])          return n - maxLen   if __name__ == "__main__":     sol = Solution()      s = "nowcoder"      # s = "aaa"      res = sol.minInsert(s)      print res