本文涉及知识点
动态规划汇总
字符串 状态机动态规划
LeetCode1320. 二指输入的的最小距离
二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。
例如字母 A 位于坐标 (0,0)，字母 B 位于坐标 (0,1)，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。
给你一个待输入字符串 word，请你计算并返回在仅使用两根手指的情况下，键入该字符串需要的最小移动总距离。
坐标 (x1,y1) 和 (x2,y2) 之间的 距离 是 |x1 - x2| + |y1 - y2|。
注意，两根手指的起始位置是零代价的，不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。
示例 1：
输入：word = “CAKE”
输出：3
解释：
使用两根手指输入 “CAKE” 的最佳方案之一是：
手指 1 在字母 ‘C’ 上 -> 移动距离 = 0
手指 1 在字母 ‘A’ 上 -> 移动距离 = 从字母 ‘C’ 到字母 ‘A’ 的距离 = 2
手指 2 在字母 ‘K’ 上 -> 移动距离 = 0
手指 2 在字母 ‘E’ 上 -> 移动距离 = 从字母 ‘K’ 到字母 ‘E’ 的距离 = 1
总距离 = 3
示例 2：
输入：word = “HAPPY”
输出：6
解释：
使用两根手指输入 “HAPPY” 的最佳方案之一是：
手指 1 在字母 ‘H’ 上 -> 移动距离 = 0
手指 1 在字母 ‘A’ 上 -> 移动距离 = 从字母 ‘H’ 到字母 ‘A’ 的距离 = 2
手指 2 在字母 ‘P’ 上 -> 移动距离 = 0
手指 2 在字母 ‘P’ 上 -> 移动距离 = 从字母 ‘P’ 到字母 ‘P’ 的距离 = 0
手指 1 在字母 ‘Y’ 上 -> 移动距离 = 从字母 ‘A’ 到字母 ‘Y’ 的距离 = 4
总距离 = 6
提示：
2 <= word.length <= 300
每个 word[i] 都是一个大写英文字母。
动态规划
vPosr和vPosc记录各字母所在行列。
动态规划规格的状态表示
dp[i][j][k] 表示处理了i个字母，两只手指分别在字母i和j的最少移动次数。
pre[j][k] = dp[i][j][k]
dp[j][k] = dp[i+1][j][k]
空间复杂度：O(n
∑
∑
\sum\sum
∑∑)，其中n = word.lenght
∑
\sum
∑ 是字符集的大小，为26。
动态规划的转移方程
任何前置状态都有只有两个转化方式。移动手指1，移动手指2。
单个状态的时间复杂度O(1)
总时间复杂度：O(n
∑
∑
\sum\sum
∑∑)
动态规划的初始状态
全部为0
动态规划的填表顺序
i = 0 : to n-1
动态规划的返回值
min(pre)
代码
核心代码
template<class ELE, class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
*seft = min(*seft, (ELE)other);
}
class Solution {
public:
int minimumDistance(string word) {
int rs[26], cs[26];
for (int i = 0; i < 26; i++) {
rs[i] = i / 6;
cs[i] = i % 6;
}
vector<vector<int>> pre(26, vector<int>(26));
for (int i = 0; i < word.length(); i++) {
const int cur = word[i] - 'A';
vector<vector<int>> dp(26, vector<int>(26, m_iNotMay));
for (int j1 = 0; j1 < 26; j1++) {
for (int j2 = 0; j2 < 26; j2++) {
const int need1 = abs(rs[j1] - rs[cur]) + abs(cs[j1] - cs[cur]);
MinSelf(&dp[cur][j2], pre[j1][j2] + need1);
const int need2 = abs(rs[j2] - rs[cur]) + abs(cs[j2] - cs[cur]);
MinSelf(&dp[j1][cur], pre[j1][j2] + need2);
}
}
pre.swap(dp);
}
int iRet = m_iNotMay;
for (const auto& v : pre) {
iRet = min(iRet, *std::min_element(v.begin(),v.end()));
}
return iRet;
}
const int m_iNotMay = 1'000'000;
};
单元测试
template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
Assert::AreEqual(v1.size(), v2.size());
for (int i = 0; i < v1.size(); i++)
{
Assert::AreEqual(v1[i], v2[i]);
}
}
template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
sort(vv1.begin(), vv1.end());
sort(vv2.begin(), vv2.end());
Assert::AreEqual(vv1.size(), vv2.size());
for (int i = 0; i < vv1.size(); i++)
{
AssertEx(vv1[i], vv2[i]);
}
}
namespace UnitTest
{
string word;
TEST_CLASS(UnitTest)
{
public:
TEST_METHOD(TestMethod0)
{
word = "AB";
auto res = Solution().minimumDistance(word);
AssertEx(0, res);
}
TEST_METHOD(TestMethod01)
{
word = "ABC";
auto res = Solution().minimumDistance(word);
AssertEx(1, res);
}
TEST_METHOD(TestMethod02)
{
word = "ABCD";
auto res = Solution().minimumDistance(word);
AssertEx(2, res);
}
TEST_METHOD(TestMethod03)
{
word = "ABM";
auto res = Solution().minimumDistance(word);
AssertEx(1, res);
}
TEST_METHOD(TestMethod04)
{
word = "ABCM";
auto res = Solution().minimumDistance(word);
AssertEx(2, res);
}
TEST_METHOD(TestMethod11)
{
word = "CAK";
auto res = Solution().minimumDistance(word);
AssertEx(2, res);
}
TEST_METHOD(TestMethod1)
{
word = "CAKE";
auto res = Solution().minimumDistance(word);
AssertEx(3, res);
}
TEST_METHOD(TestMethod20)
{
word = "HAPP";
auto res = Solution().minimumDistance(word);
AssertEx(2, res);
}
TEST_METHOD(TestMethod2)
{
word = "HAPPY";
auto res = Solution().minimumDistance(word);
AssertEx(6, res);
}
};
}
扩展阅读
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关推荐
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
