回文最少分割

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <malloc.h>
#include <limits.h>

#define MIN(X, Y) ((X) < (Y) ? (X) : (Y))
// 初始化一个动态大小的矩阵
#define INIT_MATRIX(TYPE, PTR, COL, ROW) \
    (PTR) = (TYPE **) malloc(sizeof(TYPE *) * (COL));\
    for (int i = 0; i < (COL); i++) {\
        (PTR)[i] = (TYPE *) calloc((ROW), sizeof(TYPE));\
    }
// 释放一个动态大小的矩阵
#define FREE_MATRIX(PTR, COL) \
    for (int i = 0; i < (COL); i++) {\
        free((PTR)[i]);\
    }\
    free((PTR));
#define MAXLEN 5001


int min_cut(char *str);

int main(void) {
    char str[MAXLEN];
    scanf("%s", str);
    printf("%d\n", min_cut(str));
    return 0;
}

int min_cut(char *str) {
    int n = (int) strlen(str), res;
    int *dp = (int *) malloc(sizeof(int) * (n + 1));
    bool **is_pal;
    INIT_MATRIX(bool, is_pal, n, n);
    dp[n] = -1;
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = INT_MAX;
        for (int j = i; j < n; j++) {
            if (str[i] == str[j] && ((j - i < 2) || is_pal[i + 1][j - 1])) {
                is_pal[i][j] = true;
                dp[i] = MIN(dp[i], dp[j + 1] + 1);
            }
        }
    }
    res = dp[0];
    free(dp);
    FREE_MATRIX(is_pal, n);
    return res;
}

#include <iostream>
#include <cstring>
const int N = 5e3+2;
using namespace std;
string s;
int dp[N],can[N][N];
int main(){
    ios::sync_with_stdio(false);
    cin>>s;
    int n = s.length();
    s='*'+s;
    for(int k=1;k<=n;k++){
        for(int i=1;i+k<=n;i++){
            if((can[i+1][i+k-1]||i+1>=i+k-1)&&s[i]==s[i+k])
                can[i][i+k]=1;
        }
    }
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1]+1;
        for(int j=1;j<=i;j++){
            if(can[j][i]||j==i){
                dp[i] = min(dp[i],dp[j-1]+1);
            }
        }
    }
    cout<<dp[n]-1<<endl;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    int n = s.length();
    int a[n][n] = {0}, dp[n+1]={0};
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            a[i][j] = (i==j);
            
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1] + 1;
        for(int j=i;j>=0;j--){
            if(s[i]==s[j] && (i-j<2 || a[j+1][i-1])){
                a[j][i] = 1;
                if(j==0)
                    dp[i] = min(dp[i], 0);
                else
                    dp[i] = min(dp[i], dp[j-1]+1);
            }
        }
    }
    cout<<dp[n-1]<<endl;
    return 0;
}

#include <iostream>
(720)#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    int len = s.length();
    int ishw[len][len];
    int cnt[len];
    for (int i = 0; i < len; i++) {
        cnt[i] = 0;
        for (int j = 0; j < len; j++) {
            ishw[i][j] = i == j ? 1 : 0;
        }
    }
    for (int i = 1; i < len; i++) {
        cnt[i] = cnt[i-1] + 1;
        for (int j = i; j >= 0; j--) {
            if (s[i] == s[j] && (i - j < 2 || ishw[j+1][i-1])) {
                ishw[j][i] = 1;
                cnt[i] = min(j == 0 ? 0 : cnt[j-1] + 1, cnt[i]);
            }
        }
    }
    cout << cnt[len-1] << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(getHui(s));
    }
    

    public static int getHui(String s) {
        if (s == null || s.length() == 0 || s.length() == 1)
            return 0;
        char[] str = s.toCharArray();
        //dp[i]表示在str中从[i...len-1]需要的最少分割数
        int[] dp = new int[str.length+1];
        //当整串字符串为回文结构时，确保我们可以得到正确的0
        dp[str.length] = -1;
        /*
        如果在dp[i..len-1]中有j使str[i...j]为回文结构，则dp[i] = dp[j+1]+1。
        所以dp[i] = min {dp[j+1] + 1 (i<=j<len & str[i..j]是回文)}
        */
        //check[i][j] == true 代表 str[i..j]为回文
        boolean[][] check = new boolean[str.length][str.length];
        //check[i][j]为true的三种情况：
        //1. i==j; 2.j-1 == 1时两个字符相同; 3. check[i+1][j-1]==true且str[i] == str[j]
        for (int i = dp.length-2; i >= 0; i--) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = i; j < str.length; j++) {
                if(i == j)
                    check[i][j] = true;
                else if (j - i == 1)
                    check[i][j] = str[i] == str[j];
                else
                    check[i][j] = check[i+1][j-1] && str[i]==str[j];
                if(check[i][j])
                    dp[i] = Math.min(dp[i], dp[j+1] + 1);
            }
        }
        return dp[0];
    }
}

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str=br.readLine().trim();
        System.out.print(minCut(str));
    }
    public static int minCut(String str){
        if(str==null||str.equals("")){
            return 0;
        }
        char[] chas=str.toCharArray();
        int len=chas.length;
        int[] dp=new int[len+1];
        dp[len]=-1;
        boolean[][] p=new boolean[len][len];
        for(int i=len-1;i>=0;i--){
            dp[i]=Integer.MAX_VALUE;
            for(int j=i;j<len;j++){
                if(chas[i]==chas[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];
    }
}

// JS 正确姿势
function cutStr(str) {
    const list = []; //用来存数分割后的字符串

    function checkStr(str) { //检验str是否是回文
        return str.split('').reverse().join('') === str;
    }

    var repeatCut = function (str) {
        if (checkStr(str)) { //递归出口：本身是个回文，就添加到list并返回；
            list.push(str);
            return;
        }
        for (var i = str.length; i > 0; i--) { //找出最大回文，添加到list内，剩下的继续找
            if (checkStr(str.substring(0, i + 1))) {
                list.push(str.substring(0, i + 1));
                repeatCut(str.substring(i + 1, str.length));
                break;
            }
        }
    };

    repeatCut(str);

    var count = list.length - 1;
};