题目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; }
