1320. 二指输入的的最小距离【DP，非递归】

题目

代码

package main

import "math"

// "HAPPY"
// visited[i][l][r]，i为字母下标，l为左指的键位，r为右指的键位，写完第i个字符后（左手在l，右手在r）的移动距离为visited[i][l][r]
// 当i为0时，打印了'H'，所以此时无论l和r等于几，visited[0]['H'-'A'][r]和visited[0][l]['H'-'A']都为0
// 'H'-'A'是字母'H'的下标
// eg: visited[1][l][r]表示啥意思？
// 输入完A，要不是左手指输入，要不然是r输入，所以l，r中可能有一个要是在'A'上
//
// 输完"HAPPY"后，答案是多少呢？
// visited[4][?]['Y'-'A']和visited[4]['Y'-'A'][?]中最小的
//
// 初始值（边界条件）
// 1、当i为0时，打印了'H'，所以此时无论l和r等于几，visited[0]['H'-'A'][r]和visited[0][l]['H'-'A']都为0
// 
// 2、其他情况全部置成最大值
//
// 状态转移：visited[i][l][r]
// 1、如果是左手打印的就是visited[i][word[i-1]][r] = min( visited[i-1][l?][r] + distanc(l?, [word[i-1])
// 上一步l在哪是不知道的
// 2、如果是右手打印的就是visited[i][l][word[i-1]] = min( visited[i-1][l][r?] + distanc(r?, [word[i-1])
// 上一步r在哪里也是不知道
//
// 不存在l==r的情况，即使是打印HHH，用一个手指打印肯定比用两个手机打印节省

/*
A B C D E F
G H I J K L
M N O P Q R
S T U V W X
Y Z
 */
// p q表示两个字母
// 取值范围是：'A' - 'A'到'Z' - 'A'
func distance(p, q int) int {
    return abs(p/6 - q/6) + abs(p%6 - q%6) // p、q的位置坐标: (p/6, p%6)、(q/6, q%6)
}

func abs(x int) int {
    if x < 0 {
        return 0 - x
    }

    return x
}

var visited [][26][26]int

func minimumDistance(word string) int {
    if len(word) == 0 {
        return 0
    }

    // 初始化：visited[0][x][y]全部为0，不用初始化
    visited = make([][26][26]int, len(word), len(word))
    // 先全部置为最大值
    for i:=0; i<len(word); i++ {
        for j:=0; j<26; j++ {
            for k:=0; k<26; k++ {
                visited[i][j][k] = math.MaxInt32
            }
        }
    }
    // visited[0][word[0]-'A'][x]
    // visited[0][x][word[0]-'A']
    for x:=0; x<26; x++ {
        visited[0][word[0]-'A'][x] = 0
        visited[0][x][word[0]-'A'] = 0
    }
    // 初始化结束

    // 状态转移
    for i:=1; i<len(word); i++ {
        cur := word[i] - 'A'

        for l :=0; l<26; l++ {
            for r :=0; r<26; r++ {
                // 当前状态： visited[i][cur][r]或visited[i][l][cur]
                // 上一个状态：visited[i-1][l][r]
                // 如果上一个状态不存在，当前状态就是无效的，剪枝
                if visited[i-1][l][r] == math.MaxInt32 {
                    continue
                }
                visited[i][cur][r] = min(visited[i][cur][r], visited[i-1][l][r] + distance(l, int(cur)))
                visited[i][l][cur] = min(visited[i][l][cur], visited[i-1][l][r] + distance(r, int(cur)))
            }
        }

    }

    // 寻找最小值
    var res = math.MaxInt32
    for j:=0; j<26; j++ {
        for k:=0; k<26; k++ {
            res = min(res, visited[len(word)-1][j][k])
        }
    }

    return res
}

func min(x, y int) int {
    if x < y {
        return x
    }

    return y
}