对dp 变量需要执行初始化,否者LeetCode 会出现同样的用例,单独执行可以通过,提交代码执行不通过的情况。 下面是找最长回文串的动态规划代码。 class Solution { public: string longestPalindrome(string s) { int dp[1000][1000] ={0}; // d[i][j] i 位置开始,j位置结束的子串 是否是回文串 ,这里需要初始化,否提交代码时不通过 int max = 1; // 保存最大的回文串长度 int i_max = 0; for(int j = 1; j< s.size();j++){ dp[j][j]=1; //初始化,自己肯定是回文串。 if(s[j-1] == s[j]) { // 处理回文串为2的情况。 dp[j-1][j] = 1; if(max < 2){ max = 2; i_max = j-1; } } for(int i = j-2;i >=0; i--){ // 从回文串至少是3的地方开始 if(s[i] == s[j] && dp[i+1][j-1]){ dp[i][j]=1; if(max < (j-i + 1)){ max = j - i + 1; i_max = i; } } } } return s.substr(i_max,max); } };
标签:子串,int,max,最长,dp,回文 From: https://www.cnblogs.com/daniel123/p/16658753.html