标签： 记忆化搜索

目标

给你一个 m x n 的网格 grid，其中每个单元格包含以下值之一：0、1 或 2。另给你一个整数 k。

你从左上角 (0, 0) 出发，目标是到达右下角 (m - 1, n - 1)，只能向 右 或 下 移动。

每个单元格根据其值对路径有以下贡献：

• 值为 0 的单元格：分数增加 0，花费 0。
• 值为 1 的单元格：分数增加 1，花费 1。
• 值为 2 的单元格：分数增加 2，花费 1。

返回在总花费不超过 k 的情况下可以获得的 最大分数 ，如果不存在有效路径，则返回 -1。

注意： 如果到达最后一个单元格时总花费超过 k，则该路径无效。

示例 1：

输入： grid = [[0, 1],[2, 0]], k = 1
输出： 2
解释：
最佳路径为：
单元格  grid[i][j] 当前分数 累计分数 当前花费 累计花费
(0, 0)     0         0      0        0       0
(1, 0)     2         2      2        1       1
(1, 1)     0         0      2        0       1
因此，可获得的最大分数为 2。

示例 2：

输入： grid = [[0, 1],[1, 2]], k = 1
输出： -1
解释：
不存在在总花费不超过 k 的情况下到达单元格 (1, 1) 的路径，因此答案是 -1。

说明：

• 1 <= m, n <= 200
• 0 <= k <= 10^3
• grid[0][0] == 0
• 0 <= grid[i][j] <= 2

思路

有一个 m x n 网格 grid，其元素值可取 0、1、2，从左上角 (0, 0) 移动到 (m - 1, n - )，每次移动只能向右或向下，移动的代价为 grid[i][j] == 0 ? 0 : 1。求总代价不超过 k 的条件下，从左上移动到右下的最大得分，如果不存在有效路径返回 -1。

定义 dp[i + 1][j + 1][c] 表示到达坐标 (i, j) 且代价不超过 c - 1 的最大得分。状态转移方程为 dp[i + 1][j + 1][c] = Math.max(dp[i][j + 1][c + cost], dp[i + 1][j][c + cost]) + grid[i][j]，其中 cost = grid[i][j] == 0 ? 0 : -1。

可以进行空间优化，直接将第一个维度去掉，内层倒序遍历即可。

代码

/**
 * @date 2026-04-30 8:57
 */
public class MaxPathScore3742 {

    public int maxPathScore_v2(int[][] grid, int k) {
        int n = grid[0].length;
        int[][] dp = new int[n + 1][k + 2];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        Arrays.fill(dp[1], 1, k + 2, 0);
        for (int[] row : grid) {
            for (int j = 0; j < n; j++) {
                int cost = row[j] == 0 ? 0 : -1;
                for (int c = k + 1; c >=1; c--) {
                    dp[j + 1][c] = Math.max(dp[j + 1][c + cost], dp[j][c + cost]) + row[j];
                }
            }
        }
        return dp[n][k + 1] < 0 ? -1 : dp[n][k + 1];
    }

}

性能

目标

一个魔法师有许多不同的咒语。

给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。

已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。

每个咒语最多只能被使用 一次 。

请你返回这个魔法师可以达到的伤害值之和的 最大值 。

示例 1：

输入：power = [1,1,3,4]
输出：6
解释：
可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。

示例 2：

输入：power = [7,1,6,6]
输出：13
解释：
可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。

说明：

• 1 <= power.length <= 10^5
• 1 <= power[i] <= 10^9

思路

有一个数组 power 表示咒语的伤害值，魔法师使用其中任意咒语后，就无法再使用伤害值 +1 +2 -1 -2 的咒语，每个咒语只能使用一次，求伤害值的最大值。

使用哈希表记录伤害值相同的和，创建新数组（不包含重复伤害值），根据伤害值排序。如果不选当前伤害值，状态可以从后面转移而来，如果选则从后面大于当前伤害值 + 2 的转移而来。

代码

/**
 * @date 2025-10-11 8:57
 */
public class MaximumTotalDamage3186 {

    public long maximumTotalDamage(int[] power) {
        Map<Integer, Long> sum = new HashMap<>();
        for (int i : power) {
            sum.merge(i, (long) i, Long::sum);
        }
        int n = sum.size();
        int[] powers = new int[n];
        int i = 0;
        for (Integer damage : sum.keySet()) {
            powers[i++] = damage;
        }
        Arrays.sort(powers);
        long[] mem = new long[n + 1];
        mem[n - 1] = sum.get(powers[n - 1]);
        for (int j = n - 2; j >= 0; j--) {
            int k = j;
            while (k < n && powers[k] - powers[j] <= 2) {
                k++;
            }
            mem[j] = Math.max(mem[j + 1], mem[k] + sum.get(powers[j]));
        }
        return mem[0];
    }

}

性能