程式員代碼面試指南刷題--第五章.回文最少分割

題目描述

給定一個字元串，傳回把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];
    }
}