题目

题目描述:
假设你有一条长度为5的木版,初始时没有涂过任何颜色。
你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色,用一个长度为5的字符串表示这个目标:RGBGR。
每次你可以把一段连续的木版涂成一个给定的颜色,后涂的颜色覆盖先涂的颜色。
例如第一次把木版涂成RRRRR,第二次涂成RGGGR,第三次涂成RGBGR,达到目标。 用尽量少的涂色次数达到目标。

输入描述:
输入仅一行,包含一个长度为n的字符串,即涂色目标。
字符串中的每个字符都是一个大写字母,不同的字母代表不同颜色,相同的字母代表相同颜色。

输出描述:
仅一行,包含一个数,即最少的涂色次数。


解析

1)知识点

  • 看题目易得,这是一道dp的题目,但是dp数组是啥就是一个问题了。这道题其实是一个区间dp

2)看题目

  • 题目说,我们可以一笔画一条,最少要多少下画成现在要的这个亚子(表示可以覆盖)。

3)算法分析

  1. 首先,我们确定了这是dp:动态规划最重要的就是递推和dp数组的含义
  2. 首先是dp数组的含义
    1. 这道题里面重要的是,对于这个木板,你最少画了多少下。
    2. 然后这里我们就可以假设,某一个区间里面,最少要画多少下(这样算木板就是从头到尾)。
  3. 然后就是递推了:
    1. 递推的时候我们可以分成三种情况。
    2. 假如区间长度为1,说明就一个位置,一笔就可以了,就设置为1。
    3. 否则,当左端点和右端点相等的时候,说明可以一笔从左到右
      假设这里是dp[l][r],就说明dp[l + 1][r]和dp[l][r - 1]也可以被一笔画到。
      那么也可以说dp[l][r]是由这两个延申过来的,所以dp[l][r]为他们间的较小值
    4. 但假如左右不相等呢,说明要从l画到r,肯定要有一个过渡用的点
      因为两个不同的颜色要变换过去,肯定要过渡一次呀(这个时候过渡点可以是r前面的任何点,因为过渡点也可能被覆盖了)。
      那么这个时候,我们就循环判断一遍!

4)算法操作

  1. 首先说明我们的dp数组
    int dp[MAX][MAX];//dp[left][right] = 最小次数
  2. 然后要注意,因为两个点之间本来不知道多少次,要求最小值,我们就将其初始化为正无穷:
    memset(dp, INF, sizeof dp);
  3. 接下来就是递推了:
  4. 前提,我们的双重循环第一层为len表示区间长度,第二层为l表示左端点(因为要先求出最短的,构建好了底层,才能进行dp计算)。
  5. 首先是长度为1的特判
    if (len == 1) dp[l][r] = 1;
    
  6. 然后是首尾相等的判断
    if (str[l] == str[r]) dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);
  7. 最后是首尾不相等时候的循环遍历
    else 
            for (int i = 1; i < r; i++)
                    dp[l][r] = min(dp[l][r], dp[l][i] + dp[i + 1][r]); 

5)打代码

  1. 打代码嘞!
  2. 首先还是输入。
  3. dp没什么好说的,就是开始递推就好了。
  4. 看我代码~


AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//预处理

const int MAX = 1e3 + 7;
const int INF = 0x3f3f3f3f;
string str;
int dp[MAX][MAX];//dp[left][right] = 最小次数
//全局变量

int main() {
    IOS;
    cin >> str;
    //输入

    int len_str = str.length();
    str = ' ' + str;
    memset(dp, INF, sizeof dp);
    for (int len = 1; len <= len_str; len++)
        for (int l = 1; l + len - 1 <= len_str; l++) {
            int r = l + len - 1;
            if (len == 1) dp[l][r] = 1;
            else {
                if (str[l] == str[r]) dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);
                else 
                    for (int i = 1; i < r; i++)
                        dp[l][r] = min(dp[l][r], dp[l][i] + dp[i + 1][r]);    
            }
        }
    //操作

    cout << dp[1][len_str] << endl;
    //输出
    return 0;
}
//函数体