LeetCode2472. 不重叠回文子字符串的最大数目

题目描述
给你一个字符串 sss 和一个正整数 kkk 。
从字符串 sss 中选出一组满足下述条件且不重叠的子字符串：

• 每个子字符串的长度至少为 kkk。
• 每个子字符串是一个回文串。

返回最优方案中能选择的子字符串的最大数目。
子字符串是字符串中一个连续的字符序列。
1<=k<=s.length<=20001<=k<=s.length <=20001<=k<=s.length<=2000
sss 仅由小写字母组成

示例 1
输入：s = “abaccdbbd”, k = 3
输出：2
解释：选 aba 和 dbbd

思路
动态规划
状态定义：dp[i]dp[i]dp[i]表示字符串s[0,i−1]s[0,i-1]s[0,i−1]中最大子字符串的数目。
初始状态：dp[0]=0dp[0]=0dp[0]=0
状态转移：
(1) dp[i+1]=dp[i]dp[i + 1] = dp[i]dp[i+1]=dp[i]，s[i]s[i]s[i]不参与构成满足条件的回文子字符串；
(2) dp[r+1]=max(dp[r],dp[l]+1)dp[r + 1] = max(dp[r],dp[l] + 1)dp[r+1]=max(dp[r],dp[l]+1)，s[l,r]s[l,r]s[l,r]是满足条件的回文串。

在使用中心扩展法搜索回文子字符串时，找到长度大于等于k即可停止搜索，根据贪心的思想，此时统计的数目才会最大。

代码

public int maxPalindromes(String s, int k) {int n = s.length();int[] dp = new int[n + 1];for (int t = 0; t < 2 * n - 1; t++) {int i = t / 2, j = t / 2 + t % 2;dp[i + 1] = Math.max(dp[i + 1], dp[i]);while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {if (j - i + 1 >= k) {dp[j + 1] = Math.max(dp[j], dp[i] + 1);break;}i--;j++;}}return dp[n];
}

LeetCode132. 分割回文串Ⅱ

题目描述
给你一个字符串 sss，请你将 sss 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数。
1<=s.length<=20001<=s.length <=20001<=s.length<=2000
sss 仅由小写字母组成

示例 1
输入：s = “aab”
输出：1
解释：分割一次分成 [“aa”, “b”]

思路
动态规划
状态定义：dp[i]dp[i]dp[i]表示字符串s[0,i−1]s[0,i-1]s[0,i−1]的最少分割次数。
初始状态：dp[0]=−1dp[0]=-1dp[0]=−1，因为如果 sss 本身是回文字符串不需要分割。
状态转移：dp[r+1]=min(dp[r+1],dp[r]+1,dp[l]+1)dp[r+1]=min(dp[r+1],dp[r]+1,dp[l]+1)dp[r+1]=min(dp[r+1],dp[r]+1,dp[l]+1)，s[l,r]s[l,r]s[l,r]是满足条件的回文串。

代码

public int minCut(String s) {int n = s.length();int[] dp = new int[n + 1];Arrays.fill(dp, 5000);dp[0] = -1;for (int k = 0; k < 2 * n - 1; k++) {int i = k / 2, j = k / 2 + k % 2;for (; i >= 0 && j < n && s.charAt(i) == s.charAt(j); i--,j++) {dp[j + 1] = Math.min(dp[j + 1], Math.min(dp[j] + 1, dp[i] + 1));}}return dp[n];
}

当然本题还有其他动态规划方法。

这两题在搜索回文字符串时都使用了中心扩展法。
一个长度为 nnn 的字符串，回文串的中心位置共 2n−12n-12n−1 种可能，分别为 (0,0),(0,1),(1,1),(1,2),...(k/2,k/2+k%2),...(n−2,n−2),(n−2,n−1),(n−1,n−1)(0,0),(0,1),(1,1),(1,2),...(k/2,k/2+k\%2),...(n-2,n-2),(n-2,n-1),(n-1,n-1)(0,0),(0,1),(1,1),(1,2),...(k/2,k/2+k%2),...(n−2,n−2),(n−2,n−1),(n−1,n−1)