本文共 2261 字，大约阅读时间需要 7 分钟。

两步完成DP

$dp[i][j] = \lbrace_{max(dp[i+1][j],dp[i][j-1])—if(s[i] != s[j])}^{dp[i+1][j-1]+2---------if(s[i] == s[j]} $ 有一个问题是；AC的c++代码是通过python改过的，但是Python是通不过的，很奇怪，d[2][3]在其中一步中会自己修改值，我很不理解，是它有bug,还是我的代码有bug。。。求看的人帮忙解答一下哦

//C++  AC代码class Solution {
   public:    int longestPalindromeSubseq(string s) {
           int l = s.length();        int dp[1001][1001];        memset(dp,0,sizeof(dp));        for(int i = 0;i < l;i++)            for(int j = 0;j < l;j++)                dp[i][j] = 0;        for(int i = l-1;i >= 0;i--){
               dp[i][i] = 1;            for(int j = i+1;j < l;j++){
                   if (s[i] == s[j])                    if (j-1 > i+1)                        dp[i][j] = dp[i+1][j-1] + 2;                    else if (j-1 == i+1)                        dp[i][j] = 3;                    else                        dp[i][j] = 2;                else                    dp[i][j] = max(dp[i+1][j] , dp[i][j-1]);            }        }        return dp[0][l-1];    }};

# pythonclass Solution(object):    def longestPalindromeSubseq(self, s):        """        :type s: str        :rtype: int        """        l = len(s)        dp = [[]*1001]*1001        for i in range(0,l):            for j in range(0,l):                dp[i].append(0)        for i in range(l,-1,-1):            dp[i][i] = 1            for j in range(i+1,l):                print(i,'--',j)                if s[i] is s[j]:#慢慢往下减可以不                    if j-1 > i+1:                        dp[i][j] = dp[i+1][j-1] + 2                        print('dp[',i,'][',j,'] = ',dp[i][j],i+1,j-1,dp[i+1][j-1],'----2--1--')                        print(dp[2][3],'----2--1--')                    elif j-1 == i+1:                        dp[i][j] = 3                        print('dp[',i,'][',j,'] = ',dp[i][j],'----2--2--')                        print(dp[2][3],'----2--2--')                    else:                        dp[i][j] = 2                        print('dp[',i,'][',j,'] = ',dp[i][j],'----2--3--')                        print(dp[2][3],'----2--3--')                else:                    dp[i][j] = max(dp[i+1][j] , dp[i][j-1])                    print('dp[',i,'][',j,'] = ',dp[i][j],'----max----')                    print(dp[2][3],'----max----')        return dp[0][l-1]

转载地址：http://ffmfb.baihongyu.com/