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

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