题目
题目描述: 假设你有一条长度为5的木版,初始时没有涂过任何颜色。
你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色,用一个长度为5的字符串表示这个目标:RGBGR。
每次你可以把一段连续的木版涂成一个给定的颜色,后涂的颜色覆盖先涂的颜色。
例如第一次把木版涂成RRRRR,第二次涂成RGGGR,第三次涂成RGBGR,达到目标。 用尽量少的涂色次数达到目标。 输入描述:
输入仅一行,包含一个长度为n的字符串,即涂色目标。字符串中的每个字符都是一个大写字母,不同的字母代表不同颜色,相同的字母代表相同颜色。
输出描述:
仅一行,包含一个数,即最少的涂色次数。
解析
1)知识点
- 看题目易得,这是一道dp的题目,但是dp数组是啥就是一个问题了。这道题其实是一个区间dp。
2)看题目
- 题目说,我们可以一笔画一条,最少要多少下画成现在要的这个亚子(表示可以覆盖)。
3)算法分析
- 首先,我们确定了这是dp:动态规划最重要的就是递推和dp数组的含义。
- 首先是dp数组的含义:
- 这道题里面重要的是,对于这个木板,你最少画了多少下。
- 然后这里我们就可以假设,某一个区间里面,最少要画多少下(这样算木板就是从头到尾)。
- 然后就是递推了:
- 递推的时候我们可以分成三种情况。
- 假如区间长度为1,说明就一个位置,一笔就可以了,就设置为1。
- 否则,当左端点和右端点相等的时候,说明可以一笔从左到右。
假设这里是dp[l][r],就说明dp[l + 1][r]和dp[l][r - 1]也可以被一笔画到。
那么也可以说dp[l][r]是由这两个延申过来的,所以dp[l][r]为他们间的较小值。 - 但假如左右不相等呢,说明要从l画到r,肯定要有一个过渡用的点。
因为两个不同的颜色要变换过去,肯定要过渡一次呀(这个时候过渡点可以是r前面的任何点,因为过渡点也可能被覆盖了)。
那么这个时候,我们就循环判断一遍!
4)算法操作
- 首先说明我们的dp数组:
int dp[MAX][MAX];//dp[left][right] = 最小次数
- 然后要注意,因为两个点之间本来不知道多少次,要求最小值,我们就将其初始化为正无穷:
memset(dp, INF, sizeof dp);
- 接下来就是递推了:
- 前提,我们的双重循环第一层为len表示区间长度,第二层为l表示左端点(因为要先求出最短的,构建好了底层,才能进行dp计算)。
- 首先是长度为1的特判:
if (len == 1) dp[l][r] = 1;
- 然后是首尾相等的判断:
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]);
5)打代码
- 打代码嘞!
- 首先还是输入。
- dp没什么好说的,就是开始递推就好了。
- 看我代码~
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; } //函数体