Problem Overview

This problem can be solved efficiently using interval dynamic programming. Given a string, the goal is to determine the minimum number of operations required to paint the entire string, where each operation can paint any contiguous segment.

Dynamic Programming Formulation

Define dp[l][r] as the minimum number of steps needed to completely paint the substring from index l to index r (inclusive). The final answer will be dp[0][n-1], assuming zero-based indexing.

Basee Case

A single character can always be painted in one operation:

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

Transition

Consider how to paint the interval [l, r]:

Case 1: Characters at boundaries match

If s[l] == s[r], we can paint [l, r-1] first and then extend the painting to position r without additional cost:

dp[l][r] = dp[l][r-1]

Case 2: Charactesr at boundaries differ

When s[l] != s[r], we must split the interval at some position k where l ≤ k < r. The optimal solution considers all possible split points:

dp[l][r] = min(dp[l][k] + dp[k+1][r]) for k in [l, r-1]

Complete Implementation

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string str;
    cin >> str;
    int n = str.size();
    
    vector<vector<int>> f(n, vector<int>(n, 0));
    
    for (int i = 0; i < n; i++)
        f[i][i] = 1;
    
    for (int len = 2; len <= n; len++) {
        for (int left = 0; left + len - 1 < n; left++) {
            int right = left + len - 1;
            
            if (str[left] == str[right]) {
                f[left][right] = f[left][right - 1];
            } else {
                f[left][right] = f[left][left] + f[left + 1][right];
                for (int mid = left + 1; mid < right; mid++)
                    f[left][right] = min(f[left][right], f[left][mid] + f[mid + 1][right]);
            }
        }
    }
    
    cout << f[0][n - 1] << '\n';
    return 0;
}

Complexity Analysis

The algorithm uses a three-level nested loop structure, resulting in O(n³) time complexity. The DP table requires O(n²) space. For the typical constraint of n ≤ 50, this approach performs well within limits.

Key Insight

The transition equation captures the essence of interval DP: when painting a interval, either extend a previous paint operation (when boundary colors match) or split the problem into smaller independent subproblems (when boundary colors differ).