最大点数与成本-php教程-PHP中文网

最大点数与成本

WBOY

发布： 2024-08-18 09:09:20

转载

1114人浏览过

1937 年。最大积分数量与成本

难度：中等

主题： 数组、动态规划

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

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

但是，如果您选择的单元格距离您在上一行中选择的单元格太远，您将失去分数。对于每两个相邻行 r 和 r + 1（其中 0 <= r < m - 1），在坐标 (r, c

1_{) 和 (r + 1, c}2_{) 处选取单元格将}减去 abs (c1_{- c}2_{) 来自您的分数。}

国洋商务通

Gyb2b V1.01免费版可终身使用,是一款功能强大的B2B电子商务应用软件。该软件不仅更新和修改了V1.0相关功能，更是采用了目前互联网上最流行的LAMP组合（Linux+Apache+Mysql+PHP）开发完成，模板技术实现了界面与代码的有效分离，用户可以快速地在此基础上编译模板；提供B2B电子商务应用最常见的求购、供应、商品、公司库、行业资讯、商圈、资信认证、在线交易、交易评分、留言、搜

查看详情

您能获得的最大积分。

abs(x) 定义为：

示例1：

最大点数与成本

输入： l1 = [2,4,3], l2 = [5,6,4]
输出： 9
说明：

示例2：

最大点数与成本

输入： 点 = [[1,5],[2,3],[4,2]]
输出： 11
说明：

限制：

提示：

解决方案：

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

第 1 步：定义 dp 数组

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

步骤2：初始化dp阵列

初始化第一行 dp 与第一行点相同，因为没有前面的行可以减去成本。

步骤 3：计算每行的 dp 值

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

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

步骤 4：更新每行的 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
?>

登录后复制

解释：