本文涉及知識點

動態(tài)規(guī)劃匯總
字符串 狀態(tài)機(jī)動態(tài)規(guī)劃

LeetCode1320. 二指輸入的的最小距離

二指輸入法定制鍵盤在 X-Y 平面上的布局如上圖所示，其中每個大寫英文字母都位于某個坐標(biāo)處。

例如字母 A 位于坐標(biāo) (0,0)，字母 B 位于坐標(biāo) (0,1)，字母 P 位于坐標(biāo) (2,3) 且字母 Z 位于坐標(biāo) (4,1)。
給你一個待輸入字符串 word，請你計算并返回在僅使用兩根手指的情況下，鍵入該字符串需要的最小移動總距離。
坐標(biāo) (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] 都是一個大寫英文字母。

動態(tài)規(guī)劃

vPosr和vPosc記錄各字母所在行列。

動態(tài)規(guī)劃規(guī)格的狀態(tài)表示

dp[i][j][k] 表示處理了i個字母，兩只手指分別在字母i和j的最少移動次數(shù)。
pre[j][k] = dp[i][j][k]
dp[j][k] = dp[i+1][j][k]
空間復(fù)雜度：O(n$\sum \sum$)，其中n = word.lenght $\sum$ 是字符集的大小，為26。

動態(tài)規(guī)劃的轉(zhuǎn)移方程

任何前置狀態(tài)都有只有兩個轉(zhuǎn)化方式。移動手指1，移動手指2。
單個狀態(tài)的時間復(fù)雜度O(1)
總時間復(fù)雜度：O(n$\sum \sum$)

動態(tài)規(guī)劃的初始狀態(tài)

全部為0

動態(tài)規(guī)劃的填表順序

i = 0 : to n-1

動態(tài)規(guī)劃的返回值

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

擴(kuò)展閱讀

視頻課程

先學(xué)簡單的課程，請移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成戰(zhàn)斗了，為老板分憂，請學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176

相關(guān)推薦

我想對大家說的話
《喜缺全書算法冊》以原理、正確性證明、總結(jié)為主。
按類別查閱鄙人的算法文章，請點擊《算法與數(shù)據(jù)匯總》。
有效學(xué)習(xí)：明確的目標(biāo) 及時的反饋 拉伸區(qū)（難度合適） 專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發(fā)現(xiàn)問題，早修改問題，給老板節(jié)約錢。
子墨子言之：事無終始，無務(wù)多業(yè)。也就是我們常說的專業(yè)的人做專業(yè)的事。
如果程序是一條龍，那算法就是他的是睛

測試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17
如無特殊說明，本算法用**C++**實現(xiàn)。