最大点数与成本

1937 年。花费的最大积分

难度：中等

主题：数组，动态规划

给定一个 m x n 整数矩阵点（0 索引）。从 0 点开始，您希望最大化可以从矩阵中获得的点数。

要获得积分，您必须在每一行中选择一个单元格。选择坐标 (r, c) 处的单元格将将分[r][c]添加到您的分数中。

但是，如果您选择的单元格距离您在上一行中选择的单元格太远，您将失去分数。对于每两个相邻行 r 和 r + 1（其中 0 ），选取坐标 (r, c1_{) 和 (r + 1, c} 处的单元格2) 将从您的分数中减去 _abs(c1 _{- c}2

)。

返回您可以获得的最大分数

。

abs(x) 定义为：

x 表示 x >= 0。
-x 表示 x

示例1：



• 输入：
l1 = [2,4,3], l2 = [5,6,4]
• 输出：
9
• 说明：
  蓝色单元格表示要选取的最佳单元格，其坐标为 (0, 2)、(1, 1) 和 (2, 0)。
  您的分数加上 3 + 5 + 3 = 11。
  但是，您必须从分数中减去abs(2 - 1) + abs(1 - 0) = 2。
  您的最终得分是 11 - 2 = 9。

示例2：



• 输入：
点 = [[1,5],[2,3],[4,2]]
• 输出：
11
• 说明：
  蓝色单元格表示要选取的最佳单元格，其坐标为 (0, 1)、(1, 1) 和 (2, 0)。
  您的分数加上 5 + 3 + 4 = 12。
  但是，您必须从分数中减去abs(1 - 1) + abs(1 - 0) = 1。
  您的最终得分是 12 - 1 = 11。

约束：

m == 点.长度
n == 点[r].length
• ^{1 5}
• ^{1 5}
• ^{0 5}

提示：

尝试使用动态规划。
如果点[i][j]是您最近选择的单元格，则dp[i][j]是您可以拥有的最大点数。

解决方案：

我们可以将解决方案分解为几个步骤：

第 1 步：定义 DP 数组

我们将使用二维数组 dp，其中 dp[i][j] 表示通过选择第 i 行和 j 列的单元格可以获得的最大点数。

步骤2：初始化DP阵列

将第一行 dp 初始化为与第一行点相同，因为没有之前的行来减去成本。

步骤 3：计算每行的 DP 值

对于每个后续行，我们考虑到从前一行切换的成本来计算每列的最大可能点。

为了有效计算从第 i-1 行到第 i 行的转换，我们可以使用左右两个辅助数组：

left[j] 将存储我们可以为第 j 列实现的最大值，仅考虑从左侧的转换。
right[j] 将存储我们可以为第 j 列实现的最大值，仅考虑从右侧的转换。

步骤 4：更新每行的 DP

对于第 i 行中的每列 j：

使用 left[j] 或 right[j] 中的最大值加上点 [i][j] 来更新 dp[i][j]。

步骤 5：返回最后一行的最大值

结果将是 dp 数组最后一行的最大值。

让我们用 PHP 实现这个解决方案：1937。花费的最大积分

<?php
// Example usage:
$points1 = [[1, 5], [2, 3], [4, 2]];
$points2 = [[2, 4, 3], [5, 6, 4]];
echo maxPoints($points1); // Output: 11
echo maxPoints($points2); // Output: 9
?>

解释：

• 左数组和右数组：
这些帮助我们通过考虑前一行的值来计算每个单元格可以获得的最大分数，有效地考虑跨列移动的损失。
• 动态编程方法：
此方法确保每一行都是基于前一行计算的，使解决方案可针对大型矩阵进行扩展。

这种方法的时间复杂度为 (O(m × n))，在给定约束的情况下是有效的。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是最大点数与成本的详细内容。更多信息请关注PHP中文网其他相关文章！