变回文串的最少插入次数

# -*- 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