到达目的地所需的最小初始点数

引言

在计算机科学和算法问题解决领域，人们经常会遇到需要熟练运用逻辑和数学的迷人问题。其中一个问题是在网格中找出到达目的地所需的最小起始点数，同时确保玩家的积分在整个过程中保持正数。

想象一下在一个网格中移动，每个单元格都有特定数量的积分。这些积分可以是零、负数或正数。只有当你的积分余额为正，也就是说，当你的余额大于零时，你才能在单元格之间移动。你的目标是到达特定的目标单元格，同时始终保持正积分余额。找出正确开始此旅程所需的最小起始点数是困难的部分。

示例

我们的目标是从 (0, 0) 移动到目的地单元格 (2, 2)。为了确保我们的积分余额在整个过程中保持正数，我们必须确定所需的最小起始点数。

动态规划方法

我们可以使用动态规划方法来解决这个问题。目标是生成一个与网格大小相同的二维表，即 dp。该表显示，从单元格 (i, j) 开始，到达目的地所需的最小点数由 dp[i][j] 表示。

步骤 1：基本情况

第一步是为目标单元格 (m-1, n-1) 设置基本情况。要安全到达那里，如果此单元格中的点数是正数，我们需要一个点。为了保持正余额，如果点数是负数，我们必须添加 abs(points[m-1][n-1]) + 1 个点来弥补损失。

步骤 2：填充最后一行和最后一列

之后，我们可以从目标单元格向后填充 dp 表。我们首先输入最后一行和最后一列的值来完成此操作。

为了在保持正余额的同时到达右侧的单元格，我们计算最后一行所需的最小点数。同样，我们计算最后一列所需的最小点数，以便在不变为负数的情况下到达底部单元格。

步骤 3：填充表的其余部分

现在我们可以用基本情况以及最后一行和最后一列的值填充 dp 表的其余单元格。根据离开下方单元格 (i, j+1) 和右侧单元格 (i+1, j) 所需的最低点数，我们计算离开每个单元格 (i, j) 所需的最小点数。这可以表示为

min_points_on_exit = min(dp[i + 1][j], dp[i][j + 1])

步骤 4：dp[i][j] 计算

现在让我们确定 dp[i][j] 的值。为此，请选择以下两种情况中较大的一个

• pts[i][j] 的零值表示此单元格没有增益或损失，允许玩家以与开始时相同的点数结束 (dp[i][j] = min_points_on_exit)。
• 如果 points[i][j] 为负数，则玩家在进入单元格 (i, j) 之前必须拥有超过 min_points_on_exit 的点数，以弥补损失的点数。由于 -points[i][j] 是所需的最小补偿，因此公式为 dp[i][j] = min_points_on_exit - points[i][j]。
• 如果 points[i][j] 为正数，则玩家可以以低至 min_points_on_exit - points[i][j] 的点数进入单元格 (i, j)，因为他们将在此单元格中获得 points[i][j] 的点数。但是，我们将 dp[i][j] = max(min_points_on_exit - points[i][j], 1) 以确保 min_points_on_exit - points[i][j] 不会降至零或更低。

步骤 5：最终结果

dp[0][0] 中的值表示到达目的地所需的最小起始点数，同时在整个过程中持续累积正点数。

在前面的示例中，玩家的积分在整个过程中必须保持正数。因此，所需的最小初始点数被确定为 7。

代码

输出

代码解释

最小初始点函数

• 计算在网格中（由 points[R][C] 表示）到达右下角单元格所需的最小初始点数，同时在每一步都保持正和。
• 使用动态规划（dp 数组）计算每个单元格所需的最小点数。

动态规划方法

• 从右下角单元格开始，向后迭代，计算到达每个单元格所需的最小点数。
• 确定离开当前单元格所需的最小点数，同时考虑单元格上的点数和下一个可到达单元格所需的最小点数。

主函数

• 使用特定值初始化 3x3 网格 (points)。
• 调用 minInitialPoints 查找所需的最小初始点数并打印结果。

输出

• 打印所需的最小初始点数：所需最小初始点数：7。