C++动态规划算法的应用：得到 K 个半回文串的最少修改次数 原理源码测试用例

本文涉及的基础知识点

动态规划

题目

得到 K 个半回文串的最少修改次数
给你一个字符串 s 和一个整数 k ，请你将 s 分成 k 个 子字符串 ，使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
请你返回一个整数，表示需要修改的 最少 字符数目。
注意：
如果一个字符串从左往右和从右往左读是一样的，那么它是一个 回文串 。
如果长度为 len 的字符串存在一个满足 1 <= d < len 的正整数 d ，len % d == 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 ，那么我们说这个字符串是 半回文串 。比方说 “aa” ，“aba” ，“adbgad” 和 “abab” 都是 半回文串 ，而 “a” ，“ab” 和 “abca” 不是。
子字符串 指的是一个字符串中一段连续的字符序列。
示例 1：
输入：s = “abcac”, k = 2
输出：1
解释：我们可以将 s 分成子字符串 “ab” 和 “cac” 。子字符串 “cac” 已经是半回文串。如果我们将 “ab” 变成 “aa” ，它也会变成一个 d = 1 的半回文串。
该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 1 。
示例 2:
输入：s = “abcdef”, k = 2
输出：2
解释：我们可以将 s 分成子字符串 “abc” 和 “def” 。子字符串 “abc” 和 “def” 都需要修改一个字符得到半回文串，所以我们总共需要 2 次字符修改使所有子字符串变成半回文串。
该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 2 。
示例 3：
输入：s = “aabbaa”, k = 3
输出：0
解释：我们可以将 s 分成子字符串 “aa” ，“bb” 和 “aa” 。
字符串 “aa” 和 “bb” 都已经是半回文串了。所以答案为 0 。
参数范围：
2 <= s.length <= 200
1 <= k <= s.length / 2
s 只包含小写英文字母。

分析

第一轮：vector m_aDCenger[2][101]; 四维数组：第一维,0表示奇数长度，1表示偶数长度。 第二维：d。第三维：中心。第四维半长长度。值记录变成：半回文需要改变的次数。
第二轮：int m_vNeedNum[200][201] 记录s[left,r)变成半回文需要改变的次数。
第三轮：三层循环，第一层循环：枚举k，第二层循环枚举s[0,j]。第三轮循环枚举m，[0,m]和(m,j]。
三轮时间复杂度都是：O(nnn);

核心代码

class Solution {
public:
int minimumChanges(string s, int k) {
m_c = s.length();
Init(s);
Init2(s);
vector pre(m_c);//pre[j]将s[0,j]拆分成i-1个子字符串，这些子串全部半回文的需要改变的字符数
for (int j = 0; j < m_c; j++)
{
pre[j] = m_vNeedNum[0][j + 1];
}
for (int i = 2; i <= k; i++)
{
vector dp(m_c);
for (int j = i - 1; j < m_c; j++)
{//拆分成[0,m]和(m,j]([m+1,j+1))，前者i-1个子串，后者一个子串
int iMin = INT_MAX;
for (int m = max(0,i-2); m < j; m++)
{
const int cur = pre[m] + m_vNeedNum[m + 1][j + 1];
iMin = min(iMin, cur);
}
dp[j] = iMin;
}
pre.swap(dp);
}
return pre.back();
}
void Init(std::string& s)
{
for(int i = 0 ; i < 2 ; i++ )
for (int j = 0; j <= m_c / 2; j++)
{
m_aDCenger[i][j].assign(m_c+1, vector((m_c+1)/2+1));
}
for (int d = 1; d <= m_c/2; d++)
{
for (int center = 0; center < m_c; center++)
{
int halfLen = 1;
while ((center + d* (halfLen-1) < m_c) && (center - d* (halfLen - 1) >= 0) )
{
m_aDCenger[1][d][center][halfLen] = m_aDCenger[1][d][center][halfLen - 1] +(s[center + d * (halfLen - 1)] != s[center - d * (halfLen - 1)]) ;
halfLen++;
}
}
for (int center = 0; center < m_c; center++)
{//偶数半回文
int halfLen = 1;
while ((center + d * halfLen < m_c) && (center - d * (halfLen - 1) >= 0) )
{
m_aDCenger[0][d][center][halfLen] = m_aDCenger[0][d][center][halfLen - 1] + (s[center + d * halfLen] != s[center - d * (halfLen - 1)]);
halfLen++;
}
}
}
}
void Init2(std::string& s)
{
memset(m_vNeedNum, sizeof(m_vNeedNum), 0);
for (int left = 0; left < m_c; left++)
{
for (int r = left + 1; r <= m_c; r++)
{
const int subLen = r - left;
int iNeed = 1000*1000;
for (int d = 1; (d * d <= subLen)&&(subLen >1); d++)
{
if (0 != subLen % d)
{
continue;
}
{
const int iCurNeed = DoLeftRightD(left, r, d);
iNeed = min(iNeed, iCurNeed);
}
if(d >1 )
{
const int iCurNeed = DoLeftRightD(left, r, subLen/d);
iNeed = min(iNeed, iCurNeed);
}
}
m_vNeedNum[left][r] = iNeed;
}
}
}
int DoLeftRightD(int left,int r,int d)
{
const int subLen = r - left;
const int len = subLen / d;
const auto& arr = m_aDCenger[len % 2];
const int midIndex = (len-1)/2;
int iCurNeed = 0;
for (int begin = 0; begin < d; begin++)
{
const int center = left + begin + midIndex * d;
iCurNeed += arr[d][center][(len + 1) / 2];
}
return iCurNeed;
}
int m_c;
vector m_aDCenger[2][101];
int m_vNeedNum[200][201];
};

测试用例

template
void 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]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

int main()
{
//string s = “bbacccbbaabbddddddddddddddddddddddddddddddddddddddddddddbbacccbbaabbdddddddddddddddddddddddddddddddddddddddddddddbbbacccbbaabbddddddddddddddddddddbbacccbbaabbdddddddddddddddddddddddddddddddddddddddddd”;
string s = “abcac”;
int k = 2;
Solution slu;
auto res = slu.minimumChanges(s,k);
Assert(1, res);

//CConsole::Out(res);

  • 1

}

小幅改进

空间复杂度降为O(nn)。一，预处理的时候，利用当前d，更新m_vLeftRightToNeedChange。更新完旧d的信息就不需要了。二，不需要分奇数长度和偶数长度回文。长度本身可以分奇偶了。
Init2共3层循环，时间复杂度是：O(nn)，第三层第四层，时间复杂度共O(n)。第三层循环的时间复杂度是: n/d，第四层时间复杂度是d。

新代码

class Solution {
public:
	int minimumChanges(string s, int k) {
		m_c = s.length();		
		m_vLeftRightToNeedChange.assign(m_c, vector<int>(m_c, m_iNotMay));
		for (int d = 1; d <= m_c / 2; d++)
		{
			Init(s,d);
			Init2(s,d);
		}
		vector<int> pre(m_c);//pre[j]将s[0,j]拆分成i-1个子字符串，这些子串全部半回文的需要改变的字符数
		for (int j = 0; j < m_c; j++)
		{
			pre[j] = m_vLeftRightToNeedChange[0][j];
		}
		for (int i = 2; i <= k; i++)
		{
			vector<int> dp(m_c);
			for (int j = i - 1; j < m_c; j++)
			{//拆分成[0,m]和(m,j]([m+1,j]))，前者i-1个子串，后者一个子串
				int iMin = INT_MAX;
				for (int m = max(0,i-2); m < j; m++)
				{
					const int cur = pre[m] + m_vLeftRightToNeedChange[m + 1][j];
					iMin = min(iMin, cur);
				}
				dp[j] = iMin;
			}
			pre.swap(dp);
		}
		return pre.back();
	}
	void DoCenter(int center, bool bEven,int d,const string& s)
	{
		int left = center, r = left + d*bEven;
		if (r >= m_c)
		{
			return;
		}
		m_vDLeftRightToNeedChange[left][r] = (s[left] != s[r]);
		left -= d;
		r += d;
		while ((r < m_c) && (left >= 0 ))
		{
			m_vDLeftRightToNeedChange[left][r] = m_vDLeftRightToNeedChange[left + d][r - d] + (s[left] != s[r]);
			left -= d;
			r += d;
		}
	}
	void Init(std::string& s,int d )
	{
		m_vDLeftRightToNeedChange.assign(m_c, vector<int>(m_c, m_iNotMay));		
		for (int center = 0; center < m_c; center++)
		{
			DoCenter(center, true, d,s);
			DoCenter(center, false, d,s);
		}
	}
	void Init2(std::string& s, int d)
	{		
		for (int left = 0; left < m_c; left++)
		{
			for (int iSubLen = 2; left+ iSubLen*d <= m_c ; iSubLen++)
			{
				const int r = left + iSubLen * d;
				int iNeedChange = 0;
				for (int j = 0; j < d; j++)
				{
					iNeedChange += m_vDLeftRightToNeedChange[left+j][r - d+j];
				}
				m_vLeftRightToNeedChange[left][r - 1] = min(m_vLeftRightToNeedChange[left][r - 1],iNeedChange);
			}
		}
	}	
	const int m_iNotMay = 1000 * 1000;
	int m_c;
	vector<vector<int>> m_vDLeftRightToNeedChange;//m_vDLeftRightToNeedChange[left][r]，表示当前d,str[left,left+d....r]是回文的最少次数
	vector<vector<int>> m_vLeftRightToNeedChange;//m_vLeftRightToNeedChange[left][r]表示s[left，r]变成半回文的最少改变次数
};

  • 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
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79

扩展阅读

视频课程

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

群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/133981408"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！