Palindrome Partitioning#11245

Palindrome Partitioning (Editorial)

Let $s$ be the input string. The substring $s_{i} ... s_{j}$ s_i~...~s_j is a palindrome if one of the following conditions is satisfied:

$i \geq j$ i \ge j (the substring is empty or consists of a single character);
$s_{i} = s_{j}$ s_i = s_j and the substring $s_{i + 1} ... s_{j - 1}$ s_{i+1}~...~s_{j-1} is a palindrome;

Let the function $I s P a l (i, j)$ IsPal(i, j) return $1$ if $s_{i} ... s_{j}$ s_i ... s_j is a palindrome, and $0$ otherwise. The values of $I s P a l (i, j)$ IsPal(i, j) are stored in the cells $p a l [i] [j]$ pal[i][j].

Let the function $f (i, j)$ f(i, j) return the minimum number of cuts required to partition the substring $s_{i} ... s_{j}$ s_i~...~s_j into palindromes. The values of this function will be stored in the cells of the array $d p [i] [j]$ dp[i][j]. Therefore, the solution to the problem will be $f (0, s . s i z e () - 1)$ f(0, s.size() - 1).

Note that $f (i, i) = 0$ f(i, i) = 0, as a string consisting of a single character is already a palindrome.

To compute $f (i, j)$ f(i, j), cut the substring $s_{i} ... s_{j}$ s_i~...~s_j into two parts: $s_{i} ... s_{k}$ s_i~...~s_k and $s_{k + 1} ... s_{j} (i \leq k < j)$ s_{k+1}~...~s_j~(i \le k < j). Recursively solve the problems on the strings $s_{i} ... s_{k}$ s_i~...~s_k and $s_{k + 1} ... s_{j}$ s_{k+1}~...~s_j. Look for the value of $k (i \leq k < j)$ k~(i \le k < j) that minimizes the sum $f (i, k) + f (k + 1, j) + 1$ f(i, k) + f(k + 1, j) + 1. The term $+ 1$ in the sum represents the single cut made between the characters $s_{k}$ s_k and $s_{k + 1}$ s_{k+1}. Thus, we obtain the following recurrence relation:

f (i, j) = i \leq k < j min (f (i, k) + f (k + 1, j) + 1)

f(i, j) = \min_{i \le k < j} (f(i,k) + f(k + 1, j) + 1)

Example

For example, for the string " $abab cc b$ " consisting of $7$ characters, we have:

f (1, 7) = 1 \leq k < 7 min (f (1, k) + f (k + 1, 7) + 1)

f(1, 7) = \min_{1 \le k < 7} (f(1,k) + f(k + 1, 7) + 1)

The sum takes its minimum value at $k = 3$ k = 3:

f (1, 7) = f (1, 3) + f (4, 7) + 1 = 0 + 0 + 1 = 1

f(1, 7) = f(1, 3) + f(4, 7) + 1 = 0 + 0 + 1 = 1

Since the substrings " $aba$ " and " $b cc b$ " are palindromes, $f (1, 3) = f (4, 7) = 0$ f(1, 3) = f(4, 7) = 0.

Algorithm implementation

Define the constants, the input string $s$ , and the arrays.

#define MAX 1001
#define INF 0x3F3F3F3F
int dp[MAX][MAX], pal[MAX][MAX];
string s;

The function $I s P a l (i, j)$ IsPal(i, j) checks whether the substring $s_{i} ... s_{j}$ s_i~...~s_j is a palindrome. The substring $s_{i} ... s_{j}$ s_i~...~s_j is a palindrome if $s_{i} = s_{j}$ s_i = s_j and $s_{i + 1} ... s_{j - 1}$ s_{i+1}~...~s_{j-1} is a palindrome. The values of $I s P a l (i, j)$ IsPal(i, j) are stored in the cells of the array $p a l [i] [j]$ pal[i][j].

int IsPal(int i, int j)
{
  if (i >= j) return pal[i][j] = 1;
  if (pal[i][j] != -1) return pal[i][j];
  return pal[i][j] = (s[i] == s[j]) && IsPal(i + 1, j - 1);
}

The function $f (i, j)$ f(i, j) returns the minimum number of cuts required to partition the substring $s_{i} ... s_{j}$ s_i~...~s_j into palindromes.

int f(int i, int j)
{

If $i = j$ i = j, the substring $s_{i} ... s_{j}$ s_i~...~s_j consists of a single character, and no cuts are needed. If $i > j$ i > j, the substring $s_{i} ... s_{j}$ s_i~...~s_j is considered empty, and no cuts are required.

  if (i >= j) return 0;

If the value $f (i, j)$ f(i, j) is already computed, return the stored value from the $d p [i] [j]$ dp[i][j].

  if (dp[i][j] != INF) return dp[i][j];

If the substring $s_{i} ... s_{j} (i < j)$ s_i~...~s_j~(i < j) is a palindrome, there is no need to make any cuts. In this case, the minimum number of cuts is $0$ .

  if (IsPal(i, j)) return dp[i][j] = 0;

Cut the substring $s_{i} ... s_{j}$ s_i~...~s_j into two parts: $s_{i} ... s_{k} (i \leq k)$ s_i~...~s_k~(i \le k) and $s_{k + 1} ... s_{j} (k + 1 \leq j)$ s_{k+1}~...~s_j~(k + 1 \le j). Then, recursively solve the problems for both parts: $s_{i} ... s_{k}$ s_i~...~s_k and $s_{k + 1} ... s_{j}$ s_{k+1}~...~s_j. Find the value of $k (i \leq k < j)$ k~(i \le k < j) for which the sum $f (i, k) + f (k + 1, j) + 1$ f(i, k) + f(k + 1, j) + 1 is minimized.

  for (int k = i; k < j; k++)
    dp[i][j] = min(dp[i][j], f(i, k) + f(k + 1, j) + 1);

Return the answer $d p [i] [j] = f (i, j)$ dp[i][j] = f(i, j).

  return dp[i][j];
}

The main part of the program. Read the input string.

cin >> s;

Initialize the arrays.

memset(dp, 0x3F, sizeof(dp));
memset(pal, -1, sizeof(pal));

Compute and print the answer.

res = f(0, s.size() - 1);
cout << res << endl;