生活随笔
收集整理的這篇文章主要介紹了
LeetCode 1320. 二指输入的的最小距离（动态规划）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
文章目錄
1. 題目
二指輸入法定制鍵盤在 XY 平面上的布局如上圖所示，其中每個大寫英文字母都位于某個坐標處，
例如字母 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示例
3：
輸入：word
= "NEW"
輸出：
3示例
4：
輸入：word
= "YEAR"
輸出：
7提示：
2 <= word
.length
<= 300
每個 word
[i
] 都是一個大寫英文字母。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-distance-to-type-a-word-using-two-fingers
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
2. 解題
- dp[i][c1][c2] 表示輸入完 i 字符后，手指1在 c1 字符，手指2在 c2 字符（0表示還沒有輸入字符，1-26表示A-Z）時的最小移動距離
class Solution {
public:int minimumDistance(string s
) {vector
<vector
<int>> pos(27, vector
<int>(2));int count
= 1;for(int i
= 0; i
< 5 && count
< 27; ++i
)for(int j
= 0; j
< 6 && count
< 27; ++j
){pos
[count
++] = {i
, j
};}int n
= s
.size(), mindis
= INT_MAX
;int dp
[301][27][27];memset(dp
, 0x7f, sizeof(dp
));dp
[0][s
[0]-'A'+1][0] = 0;for(int i
= 1; i
< n
; ++i
){ int c
= s
[i
]-'A'+1;for(int c1
= 1; c1
<= 26; ++c1
){for(int c2
= 0; c2
<= 26; ++c2
){if(dp
[i
-1][c1
][c2
] == 0x7f7f7f7f)continue;dp
[i
][c
][c2
] = min(dp
[i
][c
][c2
], dp
[i
-1][c1
][c2
]+abs(pos
[c
][0]-pos
[c1
][0])+abs(pos
[c
][1]-pos
[c1
][1]));if(c2
== 0)dp
[i
][c1
][c
] = min(dp
[i
][c1
][c
], dp
[i
-1][c1
][c2
]);elsedp
[i
][c1
][c
] = min(dp
[i
][c1
][c
], dp
[i
-1][c1
][c2
]+abs(pos
[c
][0]-pos
[c2
][0])+abs(pos
[c
][1]-pos
[c2
][1]));}}}for(int c1
= 1; c1
<= 26; ++c1
)for(int c2
= 0; c2
<= 26; ++c2
)mindis
= min(mindis
, dp
[n
-1][c1
][c2
]);return mindis
;}
};
32 ms 7.5 MB
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進步！
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎
總結(jié)
以上是生活随笔為你收集整理的LeetCode 1320. 二指输入的的最小距离（动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
