题解 | [CQOI2007]涂色PAINT

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = i; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }

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

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：读取输入字符串并确定其长度。
2. 初始化：创建一个二维数组 dp，并将所有长度为1的区间初始化为1。
3. 动态规划处理：从长度为2的区间开始，逐步处理更长的区间。对于每个区间 [i, j]，根据两端字符是否相同来决定状态转移方式。如果相同，则继承左端区间的值；如果不同，则遍历所有分割点，找到最小涂色次数。
4. 输出结果：最终结果为 dp[0][n-1]，即整个字符串的最小涂色次数。