小欧的最短路

[题目链接](https://www.nowcoder.com/practice/dcdac37856144dd58faf7e8c8450c8aa)

思路

小欧站在字符串的开头（位置 0），需要走到字符串的结尾（位置 $n-1$ ）。每一步有两种走法：

相邻移动：从位置 $i$ 走到位置 $i+1$ ，代价为 $|s[i] - s[i+1]|$ （ASCII 码值之差的绝对值）。
同字母跳跃：从位置 $i$ 跳到下一个与 $s[i]$ 相同的字母所在的位置 $j$ ，代价为 $2^{j-i-1}$ 。

求从位置 0 到位置 $n-1$ 的最小总代价。

动态规划

定义 $dp[i]$ 为从位置 0 到达位置 $i$ 的最小代价，初始 $dp[0] = 0$ ，其余为正无穷。

对于每个位置 $i$ ，我们有两种转移：

相邻移动： $dp[i+1] = \min(dp[i+1],\ dp[i] + |s[i] - s[i+1]|)$
同字母跳跃：设 $j$ 是位置 $i$ 之后第一个满足 $s[j] = s[i]$ 的位置，则 $dp[j] = \min(dp[j],\ dp[i] + 2^{j-i-1})$

预处理 next_same 数组

为了快速找到每个位置之后下一个相同字母的位置，我们从后往前扫描，用一个大小为 26 的数组记录每个字母最近一次出现的位置。这样 $\text{next\_same}[i]$ 就是位置 $i$ 之后第一个与 $s[i]$ 相同的位置（若不存在则为 $-1$ ）。

关于跳跃代价的溢出处理

跳跃代价为 $2^{j-i-1}$ ，当距离较大时会溢出 64 位整数。但由于相邻移动每步代价最多为 25，走 $d$ 步的代价上界为 $25d$ ，而跳跃代价 $2^{d-1}$ 增长极快，当 $d \geq 60$ 时 $2^{59}$ 已远超任何合理的路径代价，因此直接跳过即可。

样例演示

字符串 aba（ $n=3$ ）：

$dp[0] = 0$
从位置 0：相邻移动到位置 1，代价 $|a - b| = 1$ ， $dp[1] = 1$ ；跳到位置 2（下一个 a），代价 $2^1 = 2$ ， $dp[2] = 2$
从位置 1：相邻移动到位置 2，代价 $|b - a| = 1$ ， $dp[2] = \min(2, 1 + 1) = 2$

答案 $dp[2] = 2$ 。

复杂度分析

时间复杂度： $O(n)$ ，预处理 next\_same 数组和 DP 转移各遍历一次。
空间复杂度： $O(n)$ ，存储 $dp$ 数组和 $\text{next\_same}$ 数组。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    char s[200005];
    scanf("%s", s);

    vector<long long> dp(n, LLONG_MAX);
    dp[0] = 0;

    // 预处理每个位置之后下一个相同字母的位置
    int nextSame[200005];
    int last[26];
    memset(last, -1, sizeof(last));
    for (int i = n - 1; i >= 0; i--) {
        int c = s[i] - 'a';
        nextSame[i] = last[c];
        last[c] = i;
    }

    for (int i = 0; i < n - 1; i++) {
        if (dp[i] == LLONG_MAX) continue;
        // 相邻移动
        long long cost = dp[i] + abs(s[i] - s[i + 1]);
        if (cost < dp[i + 1]) dp[i + 1] = cost;
        // 同字母跳跃
        int j = nextSame[i];
        if (j != -1 && j - i - 1 < 60) {
            long long jumpCost = 1LL << (j - i - 1);
            if (dp[i] + jumpCost < dp[j])
                dp[j] = dp[i] + jumpCost;
        }
    }

    printf("%lld\n", dp[n - 1]);
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String s = br.readLine().trim();

        long[] dp = new long[n];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;

        // 预处理每个位置之后下一个相同字母的位置
        int[] nextSame = new int[n];
        int[] last = new int[26];
        Arrays.fill(last, -1);
        for (int i = n - 1; i >= 0; i--) {
            int c = s.charAt(i) - 'a';
            nextSame[i] = last[c];
            last[c] = i;
        }

        for (int i = 0; i < n - 1; i++) {
            if (dp[i] == Long.MAX_VALUE) continue;
            // 相邻移动
            long cost = dp[i] + Math.abs(s.charAt(i) - s.charAt(i + 1));
            if (cost < dp[i + 1]) dp[i + 1] = cost;
            // 同字母跳跃
            int j = nextSame[i];
            if (j != -1 && j - i - 1 < 60) {
                long jumpCost = 1L << (j - i - 1);
                if (dp[i] + jumpCost < dp[j])
                    dp[j] = dp[i] + jumpCost;
            }
        }

        System.out.println(dp[n - 1]);
    }
}