作者推荐
本文涉及知识点
动态规划 记忆化搜索 字符串
LeetCode:664 奇怪的打印机
有台奇怪的打印机有以下两个特殊要求：
打印机每次只能打印由 同一个字符 组成的序列。
每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。
示例 1：
输入：s = “aaabbb”
输出：2
解释：首先打印 “aaa” 然后打印 “bbb”。
示例 2：
输入：s = “aba”
输出：2
解释：首先打印 “aaa” 然后在第二个位置打印 “b” 覆盖掉原来的字符 ‘a’。
提示：
1 <= s.length <= 100
s 由小写英文字母组成
动态规划
空间复杂度?(n2)
时间复杂度: O(n3)
小技巧： 两个挨着的字符相同可以删除一个，不影响结果。因为打印的次数不限。 此技巧使用可以稍稍提速，不使用也没问题。
动态规范的状态表示：dp[left][r]表示 让s[left,r]符合要求的最少次数。
动态规划的转移方程：必定有一次覆盖s[left]，此次覆盖可以分以下两种情况：
- 除s[i]外，没有盖其它字符或其它字符被新的印章覆盖。dp[left][r]=1 + dp[left+1][r]
- 除s[left]外，还有字符没覆盖，假定其下标最小的为s[i]，则没印章跨越s[i]，故s(l,r)可以独立出来。dp[left][r] = dp[left+1,i-1]+dp[i][r]
动态规划的初始状态： 全部为0，表示未处理。
动态规划的填表顺序：枚举left。
动态规划的返回值：dp[0][n-1]
代码
核心代码
class Solution {
public:
int strangePrinter(string s) {
for (int i = 0; i < s.length(); i++)
{
if ((0 == i) || (s[i] != s[i - 1]))
{
m_s += s[i];
}
}
m_c = m_s.length();
m_dp.assign(m_c, vector<int>(m_c));
return Cal(0, m_c - 1);
}
int Cal(int left,int r)
{
if (left > r)
{
return 0;
}
if (0 != m_dp[left][r])
{
return m_dp[left][r];
}
int iRet = 1 + Cal(left + 1,r);
for (int i = left+1 ; i <= r; i++)
{
if (m_s[i] == m_s[left])
{
iRet = min(iRet, Cal(left + 1, i - 1) + Cal(i, r));
}
}
return m_dp[left][r] = iRet;
}
int m_c;
string m_s;
vector<vector<int>> m_dp;
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
测试用例
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
string s;
{
Solution sln;
s = "a";
auto res = sln.strangePrinter(s);
Assert(1, res);
}
{
Solution sln;
s = "aaaa";
auto res = sln.strangePrinter(s);
Assert(1, res);
}
{
Solution sln;
s = "aaabbb";
auto res = sln.strangePrinter(s);
Assert(2, res);
}
{
Solution sln;
s = "aba";
auto res = sln.strangePrinter(s);
Assert(2, res);
}
{
Solution sln;
s = "aabab";
auto res = sln.strangePrinter(s);
Assert(3, res);
}
{
Solution sln;
s = "aabacdaa";
auto res = sln.strangePrinter(s);
Assert(4, res);
}
{
Solution sln;
s = "acdddda";
auto res = sln.strangePrinter(s);
Assert(3, res);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
2023年一月版
class Solution {
public:
int strangePrinter(string s) {
m_c = s.length();
m_dp.assign(m_c + 1, vector(m_c,INT_MAX));
{
int len = 1;
for (int c = 0; c + len - 1 < m_c; c++)
{
m_dp[len][c] = 1;
}
}
for (int len = 2; len <= m_c; len++)
{
for (int c = 0; c + len - 1 < m_c; c++)
{
const int iEnd = c + len - 1;
if ((s[c] == s[iEnd]) || (s[iEnd] == s[iEnd - 1]))
{
m_dp[len][c] = m_dp[len - 1][c];
continue;
}
for (int iPreLen = 1; iPreLen < len; iPreLen++)
{
m_dp[len][c] = min(m_dp[len][c],m_dp[iPreLen][c] + m_dp[len - iPreLen][c + iPreLen]);
}
}
}
return m_dp[m_c][0];
}
vector
int m_c;
};
2023年6月版
class Solution {
public:
int strangePrinter(string s) {
m_c = s.length();
memset(m_LenBegin, 0, sizeof(m_LenBegin));
for (int begin = 0; begin < m_c; begin++)
{
m_LenBegin[1][begin] = 1;
}
for (int len = 2; len <= m_c; len++)
{
for (int begin = 0; begin + len - 1 < m_c; begin++)
{
const int end = begin + len - 1;
if (s[begin] == s[end])
{
m_LenBegin[len][begin] = m_LenBegin[len - 1][begin];
continue;
}
int iNum = INT_MAX;
for (int leftLen = 1; leftLen < len; leftLen++)
{
iNum = min(iNum, m_LenBegin[leftLen][begin] + m_LenBegin[len - leftLen][begin + leftLen]);
}
m_LenBegin[len][begin] = iNum;
}
}
return m_LenBegin[m_c][0];
}
int m_c;
int m_LenBegin[100+1][100];
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
};
2023年7月版
class Solution {
public:
int strangePrinter(string s) {
m_c = s.length();
vector
for (int len = 2; len <= m_c; len++)
{
for (int begin = 0; begin < m_c; begin++)
{
const int end = begin + len - 1;
if (end >= m_c)
{
continue;
}
if (s[begin] == s[end])
{
vLenBegin[len][begin] = vLenBegin[len-1][begin];
continue;
}
int iNum = INT_MAX;
for (int leftLen=1 ;leftLen < len ; leftLen++ )
{
iNum = min(vLenBegin[leftLen][begin] + vLenBegin[len - leftLen][begin + leftLen], iNum);
}
vLenBegin[len][begin] = iNum;
}
}
return vLenBegin[m_c][0];
}
int m_c;
};
2023年8月版
class Solution {
public:
int strangePrinter(string s) {
m_c = s.length();
m_vLeftRight.assign(m_c, vector(m_c,INT_MAX));
//任何印章方式都可以转成，第一次处理最右端元素
for (int len = 1; len <= m_c; len++)
{
#define END (left + len - 1)
for (int left = 0; END < m_c; left++)
{
if (1 == len)
{
m_vLeftRight[left][END] = 1;
continue;
}
for (int mid = left; mid < END; mid++)
{
m_vLeftRight[left][END] = min(m_vLeftRight[left][END], m_vLeftRight[left][mid] + m_vLeftRight[mid + 1][END] - (s[mid] == s[END]));
}
}
}
return m_vLeftRight.front().back();
}
int m_c;
vector
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 **C+
+17**
如无特殊说明，本算法用**C++**实现。
QQ群名片
评论记录：
回复评论：