[LeetCode]1320. Minimum Distance to Type a Word Using Two Fingers 动态规划解法

本文主要是介绍[LeetCode]1320. Minimum Distance to Type a Word Using Two Fingers 动态规划解法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述

LeetCode原题链接：1320. Minimum Distance to Type a Word Using Two Fingers

You have a keyboard layout as shown above in the X-Y plane, where each English uppercase letter is located at some coordinate.

• For example, the letter 'A' is located at coordinate (0, 0), the letter 'B' is located at coordinate (0, 1), the letter 'P' is located at coordinate (2, 3) and the letter 'Z' is located at coordinate (4, 1).

Given the string word, return the minimum total distance to type such string using only two fingers.

The distance between coordinates (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.

Note that the initial positions of your two fingers are considered free so do not count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.

Example 1:

Input: word = "CAKE"
Output: 3
Explanation: 
Using two fingers, one optimal way to type "CAKE" is: 
Finger 1 on letter 'C' -> cost = 0 
Finger 1 on letter 'A' -> cost = Distance from letter 'C' to letter 'A' = 2 
Finger 2 on letter 'K' -> cost = 0 
Finger 2 on letter 'E' -> cost = Distance from letter 'K' to letter 'E' = 1 
Total distance = 3

Example 2:

Input: word = "HAPPY"
Output: 6
Explanation: 
Using two fingers, one optimal way to type "HAPPY" is:
Finger 1 on letter 'H' -> cost = 0
Finger 1 on letter 'A' -> cost = Distance from letter 'H' to letter 'A' = 2
Finger 2 on letter 'P' -> cost = 0
Finger 2 on letter 'P' -> cost = Distance from letter 'P' to letter 'P' = 0
Finger 1 on letter 'Y' -> cost = Distance from letter 'A' to letter 'Y' = 4
Total distance = 6

Example 3:

Input: word = "NEW"
Output: 3

Example 4:

Input: word = "YEAR"
Output: 7

Constraints:

• 2 <= word.length <= 300
• word consists of uppercase English letters.

题目分析

刚看到这道题的时候还真是有点懵，想了半天两根手指怎么交叉同时输入两个相隔很远的字母呢...（第一反应两根手指是一只手上相邻的两根手指

这篇关于[LeetCode]1320. Minimum Distance to Type a Word Using Two Fingers 动态规划解法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！