矩阵中最优单元以收集最多金币

介绍

在网格中寻找最佳起始位置以收集硬币是各种计算应用程序中的典型任务。其中一个问题涉及一个网格，其中每个单元格中都有固定数量的硬币。目标是选择理想的单元格开始收集硬币，确保在遵守特定移动限制的同时获得最大总和。此主题在动态规划、游戏策略和路径优化中具有实际应用。在这篇文章中，我们研究了一种算法技术，用于确定网格中硬币收集的最佳单元格。

理解问题

想象一个网格，每个单元格都显示可用硬币的数量。你从左上角的单元格开始，只能向右或向下移动。目标是在移动到右下角单元格的同时收集最多的硬币。但这里有一个问题：一旦你到达一个单元格，你就会收集其中的所有硬币，并且该单元格不再可用于进一步收集。

算法

计算：寻找矩阵中最大硬币收集的最佳单元格

给定

• 一个 n x m 的矩阵 M，表示包含不同数量硬币的单元格。
• 一个 n x m 的 DP 表，用于存储到每个单元格为止收集到的最大累积硬币数量。

初始化

1. 初始化与网格 M 具有相似维度的 DP 表。

2. 设置 DP[0][0] = M[0][0]，因为它表示起始单元格。

计算步骤

3. 按行和列遍历网格 M（从头到尾，从左到右）。

4. 对于 M 中的每个单元格 (i, j)

a. 如果 i > 0 且 j > 0（不在第一行或第一列）

确定到单元格 (i, j) 为止可以获得的最大累积总和 DP[i][j]，考虑其相邻单元格的最大总和。

DP[i][j] = M[i][j] + max(DP[i-1][j], DP[i][j-1])

b. 如果 i = 0（第一行但不是第一列）

通过仅考虑右侧的单元格计算 DP[i][j]：DP[i][j] = M[i][j] + DP[i][j-1]

c. 如果 j = 0（第一列但不是第一行）

通过仅考虑上方的单元格计算 DP[i][j]：DP[i][j] = M[i][j] + DP[i-1][j]

d. 假设 i 和 j 都为 0（左上角单元格）

没有其他单元格需要考虑，所以 DP[i][j] = M[i][j]。

e. 当 DP 表填充完毕后，最大总累积值将存储在 DP[n-1][m-1] 中，其中 n 和 m 是框架的尺寸。

寻找最佳单元格

5. 要找到收集最多硬币的最佳单元格，请从右下角单元格 (DP[n-1][m-1]) 开始。

6. 通过选择 DP 表中其相邻单元格中具有最大累积总和的单元格，回溯到通向该单元格的路径。

7. 继续回溯，直到到达左上角单元格 (DP[0][0])。

输出

该算法识别出的理想路径表示收集最大硬币的单元格序列。

复杂度分析

• 时间复杂度：O(n * m)，其中 n 和 m 是框架的元素。
• 空间复杂度：O(n * m) 用于 DP 表。

该算法通过利用动态规划原理，有效地找到在框架中收集最大硬币的理想单元格。

示例

在一个假设情境中，我们应该考虑一个 5x5 的矩阵，表示一张藏宝图，其中每个单元格包含特定数量的硬币。我们希望探索这个矩阵以收集最大数量的硬币，同时遵守明确的移动规则。

当我们开始调查时，我们发现自己位于矩阵的左上角单元格。这是一个这样的格子的例子。

网格

• 每一步我们都可以向右或向下移动。到达一个单元格后，我们收集该单元格中的所有硬币，并且该单元格将无法用于未来的收集。
• 为了扩大我们的硬币收集量，我们利用动态规划来确定最佳路径。我们创建一个与网格具有相同维度的动态规划表（DP 表），以存储到每个单元格为止收集到的最大累积硬币数量。
• 从左上角单元格开始，我们逐行逐列遍历网格。在每个单元格，我们计算可以收集到该单元格的最大累积硬币数量。这是通过考虑其相邻单元格的最大累积总和来确定的。

我们相应地更新DP表。

DP表

• 当DP表填满后，最大的总累积量将存储在表的右下角单元格中，这表示可以收集到的最大硬币数量。在此示例中，右下角单元格的值为43。
• 为了找到导致最大硬币数量的理想路径，我们从右下角的单元格回溯到左上角的单元格。在每一步，我们选择DP表中其相邻单元格中累积总和最大的单元格。这个过程引导我们找到收集最大硬币数量的路径。

在这个模型中，理想的路径可能看起来像这样。

最佳路径

这条路径显示了我们导航以收集最大硬币数量的单元格序列。通过遵循这条路径，我们确保在探索网格的同时收集尽可能多的硬币。

实施

输出

说明

1. 输入矩阵：我们有一个表示不同字符格式的矩阵（2D 数组）
   • '0' 表示可以收集货币的空位。
   • 'C' 表示包含硬币的单元格。
   • '#' 表示不能收集货币的障碍物。
2. 总货币计数：程序遍历矩阵的每个单元格，并计算可以从该单元格及其相邻单元格收集的硬币数量。它以四个方向进行：从左到右，从右到左，从上到下，再到顶部。
3. 动态规划：它维护一个动态规划表（dp）来存储每个单元格的硬币累计计数。此表避免了重复计算。
4. 最大硬币计数：在计算累计计数之后，程序会找到可以从矩阵中任何空单元格（'0'）收集到的最大硬币计数。
5. 输出：最后，程序打印可以从矩阵中收集到的最大硬币计数。