Split String into Most Palindrome Elements

题目地址：
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=201986&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D1%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

题目：
input一个string str，方法要求split str into elements，return符合要求的最大elements数量。。这题有点怪我来写几个例子：
eg1. input: abab －》 return 2
         可以被分成 ab ｜ ab， 这样子[ab][ab]是对称的；
         但是不能分成 a | b | a | b, 因为[a][a]不对称。
eg2.input: teammate －》 return 6
        可以被分成 te | a | m | m | a | te, [te][a][m][m][a][te]是对称的
eg3: input: ab －》 return 1.
        [ab], 这直接是1
eg4: input: aaa -> reurn 3
       这个可以分成 a｜a｜a 或者直接不分： aaa。 但题目要求返回最大可能值，所以是3
eg5: 空字符串返回0.

解题思路：
这道题可以用动态规划来解。这里需要用到的是二维array。

代码：

public class SplitStringintoMostPalindromeElements {

    public static void main(String[] args){
        SplitStringintoMostPalindromeElements splitStringintoMostPalindromeElements = new SplitStringintoMostPalindromeElements();
        String s = "teammate";
        int rst = splitStringintoMostPalindromeElements.split(s);
        System.out.println(rst);
    }

    public int split(String s){
        if(s == null || s.length() <= 1){
            return 0;
        }
        int len = s.length();
        int[][] dp = new int[len][len];
        for(int i = 1; i <= len; i++){
            for(int j = 0; j <= len - i; j++){
                if(i == 1){
                    dp[j][j + i - 1] = 1;
                }
                else if(i == 2){
                    dp[j][j + i - 1] = s.charAt(j) == s.charAt(j + i - 1) ? 2 : 1;
                }
                else{
                    int left = j;
                    int right = j + i - 1;
                    int sub_len = 1;
                    while(left + sub_len <= right - sub_len){
                        String str_left = s.substring(left, left + sub_len);
                        String str_right = s.substring(right - sub_len + 1, right + 1);
                        if(str_left.equals(str_right)){
                            dp[j][j + i - 1] = Math.max(dp[j][j + i - 1], dp[left + sub_len][right - sub_len] + 2);
                        }
                        sub_len += 1;
                    }
                }
            }
        }
        return dp[0][len - 1];
    }

}