Introduction
回文串指其正向和反向相等的字符串。输入一个字符串，请将该字符串分割为一些子串，使得每个子串都是回文字符串，输出符合要求的最少的分割次数。
Input
输入为一行不包含空格的连续字符串。长度不超过100
Output
一个整数，分割次数
Sample
input
aaaaaaaaaaaaaaaa
output
0
Solution
import java.util.Scanner; public class Main { static int min; static boolean[][] dp; static char[] arr; public static void main(String[] args) { Scanner s=new Scanner(System.in); String str=s.nextLine(); arr = str.toCharArray(); int len=arr.length; dp = new boolean[len][len]; // 状态转移方程：在 s[i] == s[j] 的时候，dp[i][j] 参考 dp[i + 1][j - 1] for (int right = 0; right < len; right++) { for (int left = 0; left <= right; left++) { if (arr[left] == arr[right] && (right - left <= 2 || dp[left + 1][right - 1])) { dp[left][right] = true; } } } if(str.length()==0){ System.out.println(0); }else { min=Integer.MAX_VALUE; backtracking(0,arr.length,0); System.out.println(min-1); } } public static void backtracking(int index, int len, int count){ if(index==len){ min=Math.min(count,min); return; } for(int i=index;i<len;i++){ if(!dp[index][i])continue; count+=1; backtracking(i+1,len,count); count-=1; } return; } }
Experience
这道题真只有80分，不知道问题出在了哪里。先是使用dp找到所有的回文字符串，然后回溯统计回文字符串切割的最少次数。
