【动态规划】【数学】C++算法：514自由之路

作者推荐

【动态规划】458:可怜的小猪

涉及知识点

动态规划数学

力扣514 自由之路

电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。
给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。
最初，ring 的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。
旋转 ring 拼出 key 字符 key[i] 的阶段中：
您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。
示例 1：
输入: ring = “godding”, key = “gd”
输出: 4
解释:
对于 key 的第一个字符 ‘g’，已经在正确的位置, 我们只需要1步来拼写这个字符。
对于 key 的第二个字符 ‘d’，我们需要逆时针旋转 ring “godding” 2步使它变成 “ddinggo”。
当然, 我们还需要1步进行拼写。
因此最终的输出是 4。
示例 2:
输入: ring = “godding”, key = “godding”
输出: 13
提示：
1 <= ring.length, key.length <= 100
ring 和 key 只包含小写英文字母
保证字符串 key 一定可以由字符串 ring 旋转拼出

动态规划

** 时间复杂度 ** : O(nmm) n=key.length m等于一个字符在ring中出现的次数。
三层循环：
一层循环枚举key的字符。
二层循环当前字符的位置。
三层循环前一个字符的位置。

两个表盘位置，逆时针和顺时针最少需要转动的次数。
iMin=min(i1,i2) iMax = max(i1,i2)
min(iMax-iMin,iMin+ring.length-iMax)

动态规划的细节，方便检查


动态规划的状态表示	pre中的元素{prePos,preSetp} 按完上一个字符后，金属盘所在的位置和需要步数。
动态规划的转移方程	枚举当前字符位置和前一字符位置，计算最小值
动态规划的初始状态	{0，0}
动态规划的填表顺序	key从前到后处理,确保动态规划的无后效性
动态规划的返回值	max(preStep)

代码

核心代码

class Solution {
public:
	int findRotateSteps(string ring, string key) {
		vector<vector<int>> vCharIndexs(26);
		for (int i = 0; i < ring.length(); i++)
		{
			vCharIndexs[ring[i] - 'a'].emplace_back(i);
		}
		vector<pair<int, int>> pre;
		pre.emplace_back(0, 0);
		for (const auto& ch : key)
		{
			vector<pair<int, int>> dp;
			const auto& cur = vCharIndexs[ch - 'a'];
			for (const auto& curPos : cur)
			{
				int curStep = INT_MAX;
				for (const auto [prePos, step] : pre)
				{
					const int iMin = min(prePos, curPos), iMax = max(prePos, curPos); 
					curStep = min(curStep, step + 1 +  min(iMax - iMin, iMin + (int)ring.length() - iMax));
				}
				dp.emplace_back(curPos, curStep);
			}
			pre.swap(dp);
		}
		int iRet = INT_MAX;
		for (const auto [prePos, step] : pre)
		{
			iRet = min(iRet, step);
		}
		return iRet;
	}
};

测试用例

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 ring,  key;

	{
		Solution sln;
		ring = "godding", key = "gd";
		auto res = sln.findRotateSteps(ring, key);
		Assert(4, res);
	}
	{
		Solution sln;
		ring = "godding", key = "godding";
		auto res = sln.findRotateSteps(ring, key);
		Assert(13, res);
	}
	
		
}

2023年1月版

class Solution {
public:
int findRotateSteps(string ring, string key) {
std::unordered_map<char, vector> mCharPos;
for (int i = 0; i < ring.length(); i++)
{
mCharPos[ring[i]].push_back(i);
}
std::unordered_map<int,int> vPrePosOpeNum;//当前位置及最少操作次数
vPrePosOpeNum[0] = 0;
for (const char& ch : key)
{
std::unordered_map<int, int> vPosOpeNum;
for (const auto& pos : mCharPos[ch])
{
for (const auto& prePos : vPrePosOpeNum)
{
//大的减小的
int iMove = abs(prePos.first - pos);
iMove = min(iMove,min(prePos.first, pos) + (int)ring.length() - max(prePos.first, pos));
const int iOpeNum = iMove + prePos.second + 1;
if (vPosOpeNum.count(pos))
{
vPosOpeNum[pos] = min(vPosOpeNum[pos], iOpeNum);
}
else
{
vPosOpeNum[pos] = iOpeNum;
}
}
}
vPrePosOpeNum.swap(vPosOpeNum);
}
int iMin = INT_MAX;
for (const auto& prePos : vPrePosOpeNum)
{
iMin = min(iMin, prePos.second);
}
return (INT_MAX == iMin) ? -1 : iMin;
}
};