动态规划--最大回文子串（Python版）

最大回文子串问题
最大回文子串问题是一个经典的动态规划问题，所谓回文串，意思是正序和倒序是一样的，比如“goog”，倒过来还是“goog”。在牛客网上有这个题，题目描述如下：

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数。

例如输入分别为”abcda”,”google”，则输出为2,2。原串变为“aba”,”goog”。

有很多博客已经给出了它的C++, java代码，我们下面用Python来实现这个算法：

import sys
while True:
    s = sys.stdin.readline().strip()
    t = s[::-1] # t为s的倒序，通过逐个对比t和s的元素，来求得最长回文串
    n = len(s)
    if n == 0:
        break
    else:
        result_matrix = [[0 for i in range(n+1)] for j in range(n+1)]
        # print(result_matrix)
        # reslut[i][i]表示子串的回文子串的长度，result[n][n]表示原串的回文子串长度
        for i in range(n):
            for j in range(n):
                if s[i] == t[j]: # 如果相等，则回文串长度等于前一个状态+1
                    result_matrix[i+1][j+1] = result_matrix[i][j] + 1
                else:
                    result_matrix[i+1][j+1] = max(result_matrix[i+1][j], result_matrix[i][j+1])
        print(n-result_matrix[n][n])