LeetCode：132. 分割回文串 II • The Sejolyn Memo

状态定义#

题目要求将字符串 $s[0 \dots i]$ 切成若干段，使得每一段都是回文。

无论怎么切，最后一段 $s[j+1 \dots i]$ 必须是一个回文串。

如果我们枚举所有可能的 $j$ ，使得 $s[j+1 \dots i]$ 是回文。
那么剩下的问题就变成了：如何用最少的次数切割前面的部分 $s[0 \dots j]$ 。
而“切割 $s[0 \dots j]$ 的最少次数”正是我们之前已经计算出来的子问题 $dp[j]$ 。

因此设 $dp[i]$ 为：字符串前缀 $s[0...i]$ 的最少切割次数。

目标： $dp[n - 1]$

状态转移方程#

假设正在处理字符串 $s[0...i]$ ：

如果 $s[0...i]$ 本身就是回文，那么 $dp[i] = 0$ ，不需要切割
否则，尝试在中间某处 $j$ 切一刀。如果 $s[j+1...i]$ 是回文，那么： $dp[i] = \min(dp[i], dp[j] + 1)$
如果 $s[j + 1...i]$ 不是回文，那么无需搭理，其不是合法方案

代码实现#

public int minCut(String str) {
	char[] s = str.toCharArray();
	int n = s.length;

	// 预处理回文数组
	boolean[][] isPal = new boolean[n][n];
	for (int j = 0; j < n; ++j) {
		for (int i = 0; i <= j; ++i) {
			// 两端相等，且内部也是回文（或者内部为空）
			if (s[i] == s[j] && (j - i <= 2 || isPal[i + 1][j - 1])) {
				isPal[i][j] = true;
			}
		}
	}

	int[] dp = new int[n];
	for (int i = 0; i < n; ++i) {
		// 如果 0...i 本身就是回文串，不需要处理
		if (isPal[0][i]) {
			continue;
		}

		// 最坏情况下，前 i + 1 个字符需要切割 i 次
		dp[i] = i;
		for (int j = 0; j < i; ++j) {
			// 如果 j+1...i 是回文串，尝试在 j 后面切一刀
			if (isPal[j + 1][i]) {
				dp[i] = Math.min(dp[i], dp[j] + 1);
			}
		}
	}

	return dp[n - 1];
}

java