程序员代码面试指南刷题--第五章.回文最少分割

题目描述

给定一个字符串，返回把str全部切割成回文串的最少切割数。

输入描述:

输出包含一行字符串，代表str(1≤lengthstr≤5000)(1 \leq length_{str} \leq 5000)(1≤lengthstr​≤5000)。

输出描述:

输出一个整数，代表把str全部切割成回文串的最小切割数。

示例1

输入

ABA

输出

0
           

说明

示例2

输入

ABCBAEEE

输出

1
           

说明

切割1次，变为“ABCBA”和“EEE”
           

解法一：动态规划

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int res = getRes(s.toCharArray());
        System.out.println(res);
    }
    public static int getRes(char[] arr){
        if(arr==null||arr.length<2) return 0;
        int len = arr.length;
        int[] dp = new int[len+1];
        dp[len] = -1;
        boolean[][] p = new boolean[len+1][len+1];
        for(int i=len-1;i>=0;i--){
            dp[i] = Integer.MAX_VALUE;
            for(int j=i;j<len;j++){
                if(arr[i]==arr[j]&&(j-i<2||p[i+1][j-1])){
                    p[i][j] = true;
                    dp[i] = Math.min(dp[i],dp[j+1]+1);
                }
            }
        }
        return dp[0];
    }
}