【动态规划】【记忆化搜索】【C++算法】664. 奇怪的打印机

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

记忆化搜索 字符串

LeetCode:664 奇怪的打印机

有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印由 同一个字符 组成的序列。

每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。

给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

示例 1：

输入：s = “aaabbb”

输出：2

解释：首先打印 “aaa” 然后打印 “bbb”。

示例 2：

输入：s = “aba”

输出：2

解释：首先打印 “aaa” 然后在第二个位置打印 “b” 覆盖掉原来的字符 ‘a’。

提示：

1 <= s.length <= 100

s 由小写英文字母组成

动态规划

空间复杂度😮(n²)

时间复杂度: O(n³)

小技巧： 两个挨着的字符相同可以删除一个，不影响结果。因为打印的次数不限。 此技巧使用可以稍稍提速，不使用也没问题。

动态规范的状态表示：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(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> m_dp;};

测试用例

templatevoid Assert(const T& t1, const T& t2){	assert(t1 == t2);}templatevoid Assert(const vector& v1, const vector& 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);	}}

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 m_dp;

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];

};

2023年7月版

class Solution {

public:

int strangePrinter(string s) {

m_c = s.length();

vector vLenBegin(m_c + 1, vector(m_c+1,1));

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 m_vLeftRight;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。