BOJ. Palindrome Devision (1509)

[Link] https://www.acmicpc.net/problem/1509 · 한국어 · 日本語

Given a string s of length N, partition it into the fewest contiguous palindromic pieces. Precompute palindrome[l][r], true exactly when the inclusive substring s[l..r] is a palindrome. In increasing substring-length order, its ends must match, and either the substring has length at most two or its inner substring is already known to be a palindrome. This examines each of the O(N²) substrings once.

Use prefix DP: dp[r] is the minimum number of palindromic pieces covering the half-open prefix s[0..r). Set dp[0] = 0; for every end boundary r from 1 through N, consider each earlier boundary l. If s[l..r) is palindromic, append it to an optimal partition of the preceding prefix: dp[r] = min(dp[r], dp[l] + 1). The first character is handled by l = 0; a palindrome spanning the entire input yields dp[N] = 1. Every partition has a final palindromic piece, so considering all such l finds the optimum. Repeated characters and mixed splits need no special cases.

The palindrome table and prefix DP each use O(N²) time overall (the DP checks O(N²) possible intervals); space is O(N²) for the table and O(N) for dp. The algorithm is iterative and does not depend on recursion depth.

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        String s = input.readLine();
        int n = s.length();

        boolean[][] palindrome = new boolean[n][n];
        for (int length = 1; length <= n; length++) {
            for (int left = 0; left + length <= n; left++) {
                int right = left + length - 1;
                palindrome[left][right] = s.charAt(left) == s.charAt(right)
                        && (length <= 2 || palindrome[left + 1][right - 1]);
            }
        }

        int[] dp = new int[n + 1];
        Arrays.fill(dp, n + 1);
        dp[0] = 0;
        for (int right = 1; right <= n; right++) {
            for (int left = 0; left < right; left++) {
                if (palindrome[left][right - 1]) {
                    dp[right] = Math.min(dp[right], dp[left] + 1);
                }
            }
        }

        System.out.println(dp[n]);
    }
}