代表网站开发的logo,温州做美食网站,网站建设成本预测表,书店网站建设技术风险二维动态规划思路#xff1a; 首先#xff0c;刚做完这道题#xff1a;力扣---最长有效括号---动态规划#xff0c;栈-CSDN博客#xff0c;所以会有一种冲动#xff0c;设立g[i]#xff0c;表示以第i位为结尾的最长回文子串长度#xff0c;然后再遍历一遍取最大长度即可…
二维动态规划思路 首先刚做完这道题力扣---最长有效括号---动态规划栈-CSDN博客所以会有一种冲动设立g[i]表示以第i位为结尾的最长回文子串长度然后再遍历一遍取最大长度即可。但是后来发现如果g[i]如此表示很难得到递推公式。所以转到二维设立g[i][j]bool将其表示以第i位开头第j位结尾的子串是否是回文子串并用l和r记录到目前为止最长回文子串的左索引和右索引。所以递推公式为g[i][j]{如果s[i]s[j]且g[i1][j-1]是回文子串则为1}。此时有需要独立判断两种情况第一种情况是子串长度为1g[i][i]1第二种情况是子串长度为2(j-i1)如果s[i]s[j]则g[i][j]2。 还要说明一点为什么在二重循环时i 的顺序是从len-1到0j 的顺序是从i到len。因为由g[i1][j-1]推及g[i][j]所以我们需要先从左下角向右上角开始推行数(i)从大到小列数(j)从小到大。 代码
C
class Solution {
public:string longestPalindrome(string s) {int lens.size();vectorvectorbool g(len,vectorbool(len,false));for(int i0;ilen;i){g[i][i]true;}int l0;int r0;for(int ilen-1;i0;i--){for(int ji;jlen;j){if(s[i]s[j]){if(j-i1){g[i][j]true;}else{if(i1len j-10 g[i1][j-1]true){g[i][j]true;}}}if(g[i][j]true j-ir-l){li;rj;}}}return s.substr(l,r-l1);}
};
Python
class Solution:def longestPalindrome(self, s: str) - str:len_slen(s)g[[False for _ in range(len_s)] for _ in range(len_s)]for i in range(len_s):g[i][i]Truel0r0for i in range(len_s-1,-1,-1):for j in range(i,len_s):if s[i]s[j]:if j-i1:g[i][j]Trueelse:if i1len_s and j-10 and g[i1][j-1]True:g[i][j]Trueif g[i][j]True and j-ir-l:lirjreturn s[l:r1]
注意这句话的写法
g[[False for _ in range(len_s)] for _ in range(len_s)]
