动态规划中比较简单的实现

动态规划的原理：，讲解的非常清楚

这道题可以参考动态规划的原理，将status[i][j]的值表示为，字符串从i到j的子串是否为回文字符串，其递推公式为，如果s[i]=s[j],status[i][j]=status[i+1][j-1],否则status[i][j]=0;

详细的说明和容易出的问题放在代码注释中：

1     public String longestPalindrome(String s) 2     { 3  4         int length = s.length(); 5         if (length <= 1) { 6             return s; 7         } 8         boolean[][] temp = new boolean[length][length];//注意是Boolean类型，一开始我用的int[][]，超时，也不知道具体原因 9         //初始化数组10         for (int i = 0; i < length; i++) {11             for (int j = 0; j < length; j++) {12                 if (i >= j) {//为什么要初始化为1？如果是s[3][4]的递推公式就要依赖s[4][3],在s[3]==s[4]的情况下，当然是=1的13                     temp[i][j] = true;14                 } else {15                     temp[i][j] = false;16                 }17             }18         }19 20         int i;21         int j = 1;22         int maxlen = 0;23         int ri=0;24         int rj=0;25         while (j < length) {26             i = j - 1;27 28             while (i >= 0) {29                 if (s.charAt(i) != s.charAt(j)) {30                     temp[i][j] = false;31 32                 } else {33                     temp[i][j] = temp[i + 1][j - 1];34                     if (temp[i][j] == true && (j - i + 1) > maxlen) {35                         ri=i;//记录下来坐标，最后再直接返回，因为substring很慢，不要总用36                         rj=j;37                         maxlen = j - i+ 1;38                     }39                 }40 41                 i--;42             }43             j++;44         }45         return s.substring(ri, rj+1);46     }