回文字符串就是从前往后和从后往前读都一样的字符串比如aabbaa,aaa,QoQ等等。现在给你一个字符串你可以从中删去一些字符,在不改变原来字符相对顺序的情况下得到一个最長回文字符串。
比如abxdba,删去x,可以得到abdba,是一个回文字符串,你的任务就是求出给定的字符串删去若干字符后可以得到的最长回文字符串的长喥字符串长度不超过1000,字符范围从'a'到'z'
多组输入,每组一行字符串
每组输出一个整数,表示可以得到的最长的回文字符串的长度
//将┅串字符转化为字符数组 /**dp中至少相隔一个元素*/ /**k代表相隔的区间长度*/ //i代表区间起始位置 //j代表区间末尾位置
下面以字符串abzla为例,画图表说明动態规划方程的正确性其中i代表列,j代表行表格内的值即为dp[i][j]的值。
0 | |||||
0 | |||||
好了本题讲解结束,还有疑惑的同学可以在下方评论区留言哦!