题目1.最长回文字符串
这题为动态规划（主要是找到状态转移方程）的子序列问题
解题思路：
状态表示：dp[i][j]表示字符串的闭区间[i,j]内是否为回文字符串
状态转移方程：当s[i]==s[j]的时候
情况1：i==j；dp[i][j]为回文字符串；
情况2：j-i==1；dp[i][j]为回文字符串；
情况3：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j – 1]是否为回文字符串。
求解时i，j的顺序
如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j – 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。
所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j – 1]都是经过计算的。
提交代码：
char * longestPalindrome(char * s){
int i,j,left=0,right=0,dp[1001][1001]={0},max=0,k=0;
char *p=malloc(sizeof(char)*1001);
int len=strlen(s);
for(i=len-1;i>=0;i--)
{
for(j=i;j<len;j++)
{
if(s[i]==s[j])
{
if(j==i)
dp[i][j]=1;
if(j-i==1)
dp[i][j]=1;
if(j-i>1)
{
if(dp[i+1][j-1]==1)
{
dp[i][j]=1;
}
}
}
if(dp[i][j]==1)
{
if(j-i+1>max)
{
max=j-i+1;
left=i;
right=j;
}
}
}
}
for(i=left;i<=right;i++)
{
p[k++]=s[i];
}
p[k]='\0';
return p;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/95970.html
