题解 | #[CQOI2007]涂色PAINT#

区间dp。我也对这类题型比较陌生，只能写下自己浅薄的理解，欢迎大佬指教。
开始时对这道题没什么头绪，查阅了一些资料后写下了这段程序。不敢说已经完全理解，只记录下我写代码时的思路。

这里dp数组记录的是将第i个位置到第j个位置涂色的最少次数。初始化dp时，由于是求最小值，所以先将数组中所有元素初始化为一个极大正整数，这里用的是0x3f3f3f3f，可以替换成别的整数，够大就可以。然后将对角线上的元素，即所有的dp[i][i]初始化为1。这里也好理解，因为单独涂一个方格，自然是不多不少涂一次。
dp初始化完成后，就要开始循环计算了，这里先说一下循环框架。最外层循环，控制的是待涂***间长度。由于要从小区间开始计算，逐次合并，所以这里从1开始，表示最开始涂***间的长度设定为1。而涂色长度最大时就是待涂色的整个区间，长度为n。
中间层循环控制左侧起点的位置，从最左侧开始，直到遍历完整个待涂***间。而确定了左侧起点以及区间长度后，可以得到右侧终点，从而得到整个子区间。
外侧的两层循环已经确定了一个待确定最小值的子区间，最内侧循环的任务就是找到这个区间最少的涂色次数。这就要求最内侧循环遍历子区间内所有点，找到一个点将子区间分为两个子区间，且这两个子区间的涂色次数相加使该子区间的涂色次数最少。
三层循环的作用已经剖析完毕，整个算法的框架已经明了。再就是具体的实现细节了。在处理子区间时，当其端点处的字符相同时，则有dp[left][right]=min(dp[left+1][right],dp[left][right-1])。因为两个端点字符相同就表明颜色相同，则它们可以在一次涂色中被完成，而不应分为两个子区间去涂两次。在遍历k寻找最佳的分割点时，有dp[left][right]=min(dp[left][right],dp[left,k][k+1,right])，这一步就是在寻找最佳分割点。
最后dp中则存储了区间(i,j)最少的涂色次数，按要求返回dp[1][n]即可。
这里要注意，由于我们在申请数组时仅申请了n+1的空间(实际上n个也足够用，就是边界要特殊处理)，所以在循环控制时要特别注意，具体体现在第二层循环，left+step<=n上，这里之所以要加等号，是因为right=left+step，要覆盖到区间所有的点，必须要right到达n才行。下面这段代码是偏向C++风格的，在一些C风格的写法中，dp直接被初始化成一个足够大(远大于n)的数组，所以可以不用把边界控制的这么细，直接令left<=n即可。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(){
    string str;
    cin >> str;
    int n = str.size();
    vector<long long> temp(n + 1, 0x3f3f3f3f);
    vector<vector<long long>> dp(n + 1, temp);
    temp.clear();
    for(int i = 1;i <= n;i++){
        dp[i][i] = 1;
    }
    for(int step = 1;step <= n;step++){
        for(int left = 1;left + step <= n;left++){
            int right = left + step;
            if(str[right - 1] == str[left - 1]){
                dp[left][right] = min(dp[left + 1][right], dp[left][right - 1]);
            }
            for(int k = left;k < right;k++){
                dp[left][right] = min(dp[left][right], dp[left][k] + dp[k + 1][right]);
            }
        }
    }
    cout << dp[1][n];
}