【每日一题】涂色PAINT

题目

有一条长度为 $n$ 的木板，初始时没有涂过任何颜色。
给定一个长度为 $n$ 的字符串 $s$ ，由 R、G、B 这 3 种字符组成，分别表示红、绿、蓝这 3 种颜色。
每次可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。
求最少需要涂色多少次？

例如，给定字符串：RGBGR。第一次把木版涂成 RRRRR，第二次涂成 RGGGR，第三次涂成 RGBGR，达到目标。

解题思路

动态规划：

$dp[i][j]$ 表示将第 $i$ 块到第 $j$ 块木板涂成给定颜色，需要涂色的最少次数。

当 $i=j$ 时， $dp[i][j] = 1$ 。
当 $i < j$ 时，如果 $s[i]=s[j]$ ， $dp[i][j] = \min(dp[i+1][j], dp[i][j-1])$ ；
如果 $s[i] \neq s[j]$ ， $dp[i][j] = \min_{i \le k < j}(dp[i][k] + dp[k+1][j])$ 。

根据状态转移方程，外循环从右到左遍历 $i$ 。
最终结果返回 $dp[0][n-1]$ 。

C++代码

#include<iostream>
#include<vector>
using namespace std;

int main(){
    string s;
    cin >> s;
    const int inf = 0x3f3f3f3f;
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, inf));
    for(int i=0; i<n; ++i)
        dp[i][i] = 1;
    for(int i=n-1; i>=0; --i){
        for(int j=i+1; j<n; ++j){
            if(s[i]==s[j]){
                dp[i][j] = min(dp[i+1][j], dp[i][j-1]);
            }
            else{
                for(int k=i; k<j; ++k){
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
                }
            }
        }
    }
    cout << dp[0][n-1] << endl;
    return 0;
}