标签： 动态规划

目标

二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。

• 例如字母 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

说明：

• 2 <= word.length <= 300
• 每个 word[i] 都是一个大写英文字母。

提示：

• dp[i][j][k]: smallest movements when you have one finger on i-th char and the other one on j-th char already having written k first characters from word.

思路

使用两个手指录入 word 字符串，求移动距离的最小值。坐标 (x1, y1) 和 (x2, y2) 之间的 距离 是 |x1 - x2| + |y1 - y2|。字母的坐标见第一张图，起始位置的代价是 0。

定义 dp[i][c] 表示已录入 word[0 ~ i] 且另一个手指在字母 c 的最小移动距离。

假设当前字母编号 cur = word[i] - 'A', 前一个位置的字母编号 prev = word[i - 1] - 'A'，有 dp[i][c] = Math.min(dp[i - 1][c] + dis[prev][cur], dp[i - 1][cur] + dis[prev][c])。

已录入 word[0 ~ i] 两个手指的所在的字母一个是 cur，一个是 c，可以从两个状态转移过来：

• 一手指在字母 c 不动，一根手指从 prev 移动到 cur
• 一手指在字母 cur 不动，一根手指从 prev 移动到 c

代码

/**
 * @date 2026-04-13 10:24
 */
public class MinimumDistance1320 {

    public int minimumDistance(String word) {
        int n = word.length();
        int[][] dp = new int[n][26];
        for (int i = 1; i < n; i++) {
            int prev = word.charAt(i - 1) - 'A';
            int cur = word.charAt(i) - 'A';
            for (int c = 0; c < 26; c++) {
                dp[i][c] = Math.min(dp[i - 1][c] + dis[prev][cur], dp[i - 1][cur] + dis[prev][c]);
            }
        }
        int res = Integer.MAX_VALUE;
        for (int d : dp[n - 1]) {
            res = Math.min(res, d);
        }
        return res;
    }

}

性能

目标

一条无限长的直线上分布着一些机器人和墙壁。给你整数数组 robots ，distance 和 walls：

• robots[i] 是第 i 个机器人的位置。
• distance[i] 是第 i 个机器人的子弹可以行进的 最大 距离。
• walls[j] 是第 j 堵墙的位置。

每个机器人有 一颗 子弹，可以向左或向右发射，最远距离为 distance[i] 米。

子弹会摧毁其射程内路径上的每一堵墙。机器人是固定的障碍物：如果子弹在到达墙壁前击中另一个机器人，它会 立即 在该机器人处停止，无法继续前进。

返回机器人可以摧毁墙壁的 最大 数量。

注意：

• 墙壁和机器人可能在同一位置；该位置的墙壁可以被该位置的机器人摧毁。
• 机器人不会被子弹摧毁。

示例 1:

输入: robots = [4], distance = [3], walls = [1,10]
输出: 1
解释:
robots[0] = 4 向 左 发射，distance[0] = 3，覆盖范围 [1, 4]，摧毁了 walls[0] = 1。
因此，答案是 1。

示例 2:

输入: robots = [10,2], distance = [5,1], walls = [5,2,7]
输出: 3
解释:
robots[0] = 10 向 左 发射，distance[0] = 5，覆盖范围 [5, 10]，摧毁了 walls[0] = 5 和 walls[2] = 7。
robots[1] = 2 向 左 发射，distance[1] = 1，覆盖范围 [1, 2]，摧毁了 walls[1] = 2。
因此，答案是 3。

示例 3:

输入: robots = [1,2], distance = [100,1], walls = [10]
输出: 0
解释:
在这个例子中，只有 robots[0] 能够到达墙壁，但它向 右 的射击被 robots[1] 挡住了，因此答案是 0。

说明:

• 1 <= robots.length == distance.length <= 10^5
• 1 <= walls.length <= 10^5
• 1 <= robots[i], walls[j] <= 10^9
• 1 <= distance[i] <= 10^5
• robots 中的所有值都是 互不相同 的
• walls 中的所有值都是 互不相同 的

思路

无限长的直线上分布着一些机器人（位于 robots[i]）和墙壁 （位于 walls[j]），机器人可以向左或向右发射一枚子弹，位于 robots[i] 的机器人发射的子弹最多可以行进 distance[i]。子弹会摧毁其射程内路径上的每一堵墙，子弹不能摧毁或穿过机器人，求摧毁墙的最大数目。所有机器人的位置都是互不相同的，所有墙的位置也是互不相同的。

根据机器人的位置排序，考虑相邻机器人可以摧毁的墙的数目。定义 dp[i][k] 表示前 i 个机器人摧毁墙的最大数目，且第 i 个机器人朝 k 发射子弹，k = 0 表示向左， k = 1 表示向右。walls(from, to) 表示区间 [from, to] 内的墙的个数。

• dp[i][0] = max(dp[i - 1][0] + walls(max(prev + 1, cur - dcur), cur), dp[i - 1][1] + walls(max(prev + dprev + 1, cur - dcur), cur))

• dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + walls(cur, min(cur + dcur, next - 1))

• 当前机器人向左射，需要考虑前一个机器人的射击方向，如果前一个机器人也向左射，只需考虑区间 [max(prev + 1, cur - dcur), cur] 中墙的个数，如果向右射则需要考虑 [max(prev + dprev + 1, cur - dcur), cur] 中墙的个数。其中 dcur 表示位于 cur 的机器人的射击距离，dprev 表示位于 prev 机器人的射击距离。

• 当前机器人向右射，无需考虑前一个机器人的射击方向，取二者最大的即可，当前机器人向右射的范围是 [cur, min(cur + dcur, next - 1)]，注意特殊处理最后一个机器人，没有 next 时取 Integer.MAX_VALUE。

剩下的问题是如何快速获取区间内墙的数量，由于不涉及更新，可以直接二分获得上下界。

代码

/**
 * @date 2026-04-03 10:14
 */
public class MaxWalls3661 {

    public int maxWalls(int[] robots, int[] distance, int[] walls) {
        Arrays.sort(walls);
        int n = robots.length;
        Integer[] index = new Integer[n];
        Arrays.setAll(index, i -> i);
        Arrays.sort(index, (a, b) -> robots[a] - robots[b]);
        int[][] dp = new int[n][2];
        Integer first = index[0];
        dp[0][0] = getWalls(walls, robots[first] - distance[first], robots[first]);
        dp[0][1] = getWalls(walls, robots[first], Math.min(robots[first] + distance[first], n > 1 ? robots[index[1]] - 1 : Integer.MAX_VALUE));
        for (int i = 1; i < n; i++) {
            Integer cur = index[i];
            Integer prev = index[i - 1];
            dp[i][0] = Math.max(dp[i - 1][0] + getWalls(walls, Math.max(robots[prev] + 1, robots[cur] - distance[cur]), robots[cur]),
                    dp[i - 1][1] + getWalls(walls, Math.max(robots[cur] - distance[cur], robots[prev] + distance[prev] + 1), robots[cur]));
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]) + getWalls(walls, robots[cur], Math.min(robots[cur] + distance[cur], i < n - 1 ? robots[index[i + 1]] - 1 : Integer.MAX_VALUE));
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }

    /**
     * 获取 [from, to] 之间的墙的数量
     */
    public int getWalls(int[] walls, int from, int to) {
        int r = upperBound(walls, to);
        int l = lowerBound(walls, from);
        if (r < l) {
            return 0;
        }
        return r - l + 1;
    }

    /**
     * 返回 <= target 的最大下标
     */
    public int upperBound(int[] walls, int target) {
        int l = 0, r = walls.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (walls[m] <= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }

    /**
     * 返回 >= target 的最小下标
     */
    public int lowerBound(int[] walls, int target) {
        int l = 0, r = walls.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (walls[m] >= target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

}

性能

目标

给你一个 m x n 的网格。一个机器人从网格的左上角 (0, 0) 出发，目标是到达网格的右下角 (m - 1, n - 1)。在任意时刻，机器人只能向右或向下移动。

网格中的每个单元格包含一个值 coins[i][j]：

• 如果 coins[i][j] >= 0，机器人可以获得该单元格的金币。
• 如果 coins[i][j] < 0，机器人会遇到一个强盗，强盗会抢走该单元格数值的 绝对值 的金币。

机器人有一项特殊能力，可以在行程中 最多感化 2个单元格的强盗，从而防止这些单元格的金币被抢走。

注意：机器人的总金币数可以是负数。

返回机器人在路径上可以获得的 最大金币数 。

示例 1：

输入： coins = [[0,1,-1],[1,-2,3],[2,-3,4]]
输出： 8
解释：
一个获得最多金币的最优路径如下：
从 (0, 0) 出发，初始金币为 0（总金币 = 0）。
移动到 (0, 1)，获得 1 枚金币（总金币 = 0 + 1 = 1）。
移动到 (1, 1)，遇到强盗抢走 2 枚金币。机器人在此处使用一次感化能力，避免被抢（总金币 = 1）。
移动到 (1, 2)，获得 3 枚金币（总金币 = 1 + 3 = 4）。
移动到 (2, 2)，获得 4 枚金币（总金币 = 4 + 4 = 8）。

示例 2：

输入： coins = [[10,10,10],[10,10,10]]
输出： 40
解释：
一个获得最多金币的最优路径如下：
从 (0, 0) 出发，初始金币为 10（总金币 = 10）。
移动到 (0, 1)，获得 10 枚金币（总金币 = 10 + 10 = 20）。
移动到 (0, 2)，再获得 10 枚金币（总金币 = 20 + 10 = 30）。
移动到 (1, 2)，获得 10 枚金币（总金币 = 30 + 10 = 40）。

说明：

• m == coins.length
• n == coins[i].length
• 1 <= m, n <= 500
• -1000 <= coins[i][j] <= 1000

思路

有一个 m x n 的网格图，一个机器人从左上角 (0, 0) 向右或者向下移动直到 (m - 1, n - 1)。在此过程中可以收集对应格子上的金币，如果金币大于等于 0，则收集对应数量的金币，否则失去对应数量的金币。机器人有两次机会避免失去金币（感化），求可以获得的最大金币数量。

定义 dp[i][j][k] 表示到达 (i, j) 最多感化 k 次收集到的最大金币数，状态转移方程为：

• dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i][j - 1][0]) + coins[i][j]，不感化从上方与左方转移而来，加上当前格子金币
• dp[i][j][1] = Math.max(Math.max(dp[i - 1][j][0], dp[i][j - 1][0]), Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) + coins[i][j])，感化，不计入当前格子金币，感化次数加一，不感化，计入当前格子金币，感化次数不变
• dp[i][j][2] = Math.max(Math.max(dp[i - 1][j][1], dp[i][j - 1][1]), Math.max(dp[i - 1][j][2], dp[i][j - 1][2]) + coins[i][j])，同上

代码

/**
 * @date 2026-04-02 8:44
 */
public class MaximumAmount3418 {

    public int maximumAmount(int[][] coins) {
        int m = coins.length;
        int n = coins[0].length;
        int[][][] dp = new int[m][n][3];
        dp[0][0][0] = coins[0][0];
        dp[0][0][1] = Math.max(0, coins[0][0]);
        dp[0][0][2] = Math.max(0, dp[0][0][1]);
        for (int j = 1; j < n; j++) {
            dp[0][j][0] = dp[0][j - 1][0] + coins[0][j];
            dp[0][j][1] = Math.max(dp[0][j - 1][0], dp[0][j - 1][1] + coins[0][j]);
            dp[0][j][2] = Math.max(dp[0][j - 1][1], dp[0][j - 1][2] + coins[0][j]);
        }
        for (int i = 1; i < m; i++) {
            dp[i][0][0] = dp[i - 1][0][0] + coins[i][0];
            dp[i][0][1] = Math.max(dp[i - 1][0][0], dp[i - 1][0][1] + coins[i][0]);
            dp[i][0][2] = Math.max(dp[i - 1][0][1], dp[i - 1][0][2] + coins[i][0]);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i][j - 1][0]) + coins[i][j];
                dp[i][j][1] = Math.max(dp[i - 1][j][0], dp[i][j - 1][0]);
                dp[i][j][1] = Math.max(dp[i][j][1], Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) + coins[i][j]);
                dp[i][j][2] = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]);
                dp[i][j][2] = Math.max(dp[i][j][2], Math.max(dp[i - 1][j][2], dp[i][j - 1][2]) + coins[i][j]);
            }
        }
        return dp[m - 1][n - 1][2];
    }

}

性能