输出包含一行字符串,代表str。
输出一个整数,代表把str全部切割成回文串的最小切割数。
ABA
0
本身是回文串,不需要切割,直接输出0
ABCBAEEE
1
切割1次,变为“ABCBA”和“EEE”
时间复杂度,额外空间复杂度。
#include<iostream> #include<cstring> using namespace std; int main(void){ string str; while(cin>>str){ int len = str.size(); int isRound[len][len]; memset(isRound,0,sizeof(isRound)); int dp[len+1]; dp[-1] = -1; for(int i = 0;i<len;i++){ dp[i] = i; for(int j = i;j>=0;j--){ if(str[i]==str[j]&&(i-j<2||isRound[j+1][i-1])){ isRound[j][i] = 1; dp[i] = (dp[i]<dp[j-1]+1?dp[i]:dp[j-1]+1); } } } cout<<dp[len-1]<<endl; } }
#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; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { private static boolean[][] isPalindrome; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] str = br.readLine().toCharArray(); // 预处理,先弄一个能够查询str[i:j]是否是回文串的二维表 int n = str.length; isPalindrome = new boolean[n][n]; for(int i = 0; i < n; i++) Arrays.fill(isPalindrome[i], true); for(int i = n - 2; i >= 0; i--){ for(int j = i + 1; j < n; j++) isPalindrome[i][j] = str[i] == str[j] && isPalindrome[i + 1][j - 1]; } // 递归求解最小分割数 System.out.println(process(str, 0)); } private static int process(char[] str, int i) { if(i == str.length) return 0; int minCut = Integer.MAX_VALUE; // i依次作为str上第一段回文的结尾 for(int end = i; end < str.length; end++) if(isPalindrome[i][end]) minCut = Math.min(minCut, 1 + process(str, end + 1)); return minCut; } }process(str,i)表示的就是str从i开始,将后面切分为回文子串所需要的最少切割数,因此题目要求的就是process(str,0)。当然,我们要保证切割之后的每一段都是回文串,因此只考虑0~i已经是回文串的情况。而如果0~i已经是回文串了,就可以调用process(str,i+1)计算出将str从i+1到末尾切割成回文串的最少切割数的基础上,把0~i切出来的那一次切割加进来就行了,遍历所有可能的切割点i,选出代价最小的。然后我们根据递归的逻辑就能够改出如下的动态规划版本:
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; public class Main { private static boolean[][] isPalindrome; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] str = br.readLine().toCharArray(); // 预处理,先弄一个能够查询str[i:j]是否是回文串的二维表 int n = str.length; boolean[][] isPalindrome = new boolean[n][n]; for(int i = 0; i < n; i++) Arrays.fill(isPalindrome[i], true); for(int i = n - 2; i >= 0; i--){ for(int j = i + 1; j < n; j++) isPalindrome[i][j] = str[i] == str[j] && isPalindrome[i + 1][j - 1]; } // 动归求解最小分割数 int[] dp = new int[n]; for(int i = n - 1; i >= 0; i--){ dp[i] = Integer.MAX_VALUE; for(int j = i; j < n; j++){ if(isPalindrome[i][j]) dp[i] = Math.min(dp[i], j < n - 1? 1 + dp[j + 1]: 0); } } System.out.println(dp[0]); } }
#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.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str = scanner.nextLine(); int result = minC(str); System.out.println(result); } public static boolean[][] isPal(String s) { boolean[][] pal = new boolean[s.length()][s.length()]; int len = s.length(); for(int i = len-1; i >= 0; i --) { for(int j = i; j < len; j ++) { if(i == j) { //只有一个字符时 pal[i][j] = true; }else if(i+1 == j) { //只有两个字符时 pal[i][j]= s.charAt(i)==s.charAt(j); }else{ pal[i][j] = pal[i+1][j-1] && s.charAt(i)==s.charAt(j); } } } return pal; } public static int minC(String str) { boolean[][] pal = isPal(str); //接受保存字符串回文情况的二维数组 int[] minC = new int[str.length()+1]; //初始状态: for(int i = 0; i <= str.length(); i ++) { minC[i] = i-1; } //更新长度为i的最小剪切数: for(int i = 2; i <= str.length(); i ++) { //判断整体长度为i的字符串是否回文 if(pal[0][i-1]) { // 直接获取0-i区间的回文情况 minC[i] = 0; continue; } //判断j至i区间字符串是否回文 for(int j = 0; j < i; j ++) { if(pal[j][i-1]) { // 直接获取j至i区间的回文情况 minC[i] = Math.min(minC[i], minC[j]+1); } } } return minC[str.length()]; } }
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; };
//思路1:闭包+递归 function cutStr(str) { list = []; //用来存数分割后的字符串 function checkStr(str) { //检验str是否是回文 let rStr = str.split('').reverse().join(''); if (str === rStr) { return true; } return false; } 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)); } } }; repeatCut(str); var count = list.length - 1; return { list, count }; };