Leetcode 516 python 解题报告

python代码：

class Solution(object):    def longestPalindromeSubseq(self, s):        """        :type s: str        :rtype: int        """        dp = [[0 for i in range(len(s))] for i in range(len(s))]        for i in range(len(s)):            dp[i][i] = 1        for i in range(1,len(s)):            for j in range(i-1,-1,-1):                if s[i] == s[j]:                    dp[j][i] = 2+dp[j+1][i-1]                else:                    dp[j][i]=max(dp[j+1][i],dp[j][i-1])        return dp[0][len(s)-1]结果Time limit exceeded，思路：dp[i][j]代表从i到j的子串中，最大的回文子串长度。dp[i][i]，只有一个字母，一定是回文且长度为1。从dp[0][1]开始遍历，dp[2][1],dp[2][0],dp[3][2],dp[3][1],dp[3][0]的顺序遍历，如果si和sj相等，那j到i间最短的回文子串也至少是2，再加上j+1到i-1之间的回文子串，可以拼成一个新的回文子串，因此长度也要相加。如果si和sj不相等，则dp[j][i]等于去掉si或sj后能获得的最长回文子串的长度。
参考http://www.cnblogs.com/93scarlett/p/6385602.html后改为C++代码，成功。
AC代码：
class Solution {public:    int longestPalindromeSubseq(string s) {        int n = s.size();        int dp[n][n]={0};       for(int i = 0; i < n; i++){            dp[i][i] = 1;        }        for(int j = 1; j < n; j++){//j从1开始            //for(int i = 0; i < j; i++){            for(int i = j - 1; i >= 0; i--){                //if(s[i] == s[j] && i + 1 <= j - 1){                if(s[i] == s[j]){                    dp[i][j] = 2 + dp[i + 1][j - 1];                }else{                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);                }            }        }        return dp[0][n - 1];    }};