C++ 金矿问题

黄金矿工问题 提出了对动态规划所衍生的课程至关重要的思想，包括优化、决策和状态转移概念。在现实世界问题中，该问题的基于网格的布局和移动限制使其能够用于资源规划和在每个决策点通过有限选择进行导航等任务。

有一个概念称为黄金矿工问题，这是一个 动态规划 问题，涉及到二维网格中的累积。在我看来，矿井被设计成一个 n x m 的网格，每个单元格都包含一定量的黄金。它们的区别在于，在 矩阵 中，你并不总是从第一行开始，而是可以从第一列的任何一行获取黄金。目标是到达最后一列，并且你越能在穿越该区域时收集越多的黄金，就越好。但是，每一步的移动都受到三个方向的限制：

• 向右 (→)： 可以从单元格 (i, j) 转移到 (i, j+1)，即直接向右。
• 右上对角线 (↗)： 可以从单元格 (i, j) 移动到 (i-1, j+1)，即向右并向上（除非是第一行）。
• 右下对角线 (↘)： 从单元格 (i,j) 开始，如果不在最底行，可以移动到 (i+1, j+1)，即向右并向下。

在其实际应用中，黄金矿工问题可以作为日常生活中各种实际问题的模型。基于网格的移动在需要资源规划、物流以及在封闭或受限区域内移动的领域都有实际应用。例如，它们可以用于定义许多配送公司使用的路线，因为有些道路会带来更多的资源（或利润）产出。

除了清晰地说明如何将一个大问题分解成可以单独解决的子问题（这是动态规划的基本基本原理之一）之外，它还提供了一种处理许多领域（如经济学、运筹学、计算机科学等）优化问题的通用方法。黄金矿工问题可以被认为是一个重要的模型，它展示了理论方法如何与现实世界的决策过程相互关联。

问题概述

矿井网格的各个单元格也含有黄金，所获得的黄金数量取决于网格路径。问题是从第一列找到一条路径到最后一列，以尽可能多地收集黄金，但需遵守给定的移动规则。你可以从第一列的任何一行开始，并在最后一列的任何一行结束。

难点在于优化穿越矿井的路径，因为每一步都有多种可能性：你可以向右、向右上对角线或向右下对角线移动。如果我们计算矿井中所有可能的移动方式，对于较大的网格，这将意味着计算大量可能的路径，这是指数级的，因此不可行。这就是动态规划发挥作用的地方。

动态规划方法

最后，使用动态规划 (DP) 解决方案可以更有效地解决该问题。在这种情况下，会构建一个 DP 表，对于表的每个单元格，条目 dp[i][j] 存储到达单元格 (i, j) 时可以获得的最大黄金量。每个单元格的值是根据三个前置单元格（即右侧单元格、右对角线单元格和右下对角线单元格）可以收集的最大黄金量计算得出的。因此，所提出的问题被分解为许多重叠的子问题，并按顺序解决。

最后一个选项是在 DP 表填充了最大值之后，从 DP 表的第一列中获得的。此值是从第一列的任何一行开始，并在最后一列的任何一行结束时可以收集到的最大黄金量。

程序

让我们用一个 C++ 程序来说明黄金矿工问题。

输出

 
Gold Mine Grid:
1 3 1 5 
2 2 4 1 
5 0 2 3 
0 6 1 2 
Maximum gold collectible in gold mine 1: 16
Gold Mine Grid:
10 33 13 15 
22 21 4 1 
5 0 2 3 
0 6 14 2 
Maximum gold collectible in gold mine 2: 83
Gold Mine Grid:
1 3 1 5 9 2 
2 2 4 1 8 6 
5 0 2 3 7 4 
0 6 1 2 5 8 
4 2 1 9 10 3 
Maximum gold collectible in gold mine 3: 39
Gold Mine Grid:
0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 
Maximum gold collectible in gold mine 4: 0
Gold Mine Grid:
4 5 8 9 3 1 2 
6 7 1 4 9 5 8 
9 3 6 2 5 7 4 
2 4 7 8 1 6 9 
8 6 3 1 2 4 5 
5 9 4 6 7 3 2 
Maximum gold collectible in gold mine 5: 58   

说明

• 库和命名空间：代码首先包含标准库，如 <iostream>、<vector> 和 <algorithm>。这些库提供了基本的输入输出功能、容器管理（此处为二维向量）以及像 std::max 这样用于查找多个数字中最大值的算法实用程序。声明使用 namespace std 以避免在标准库函数前加上 std:: 前缀，从而简化代码。
• getMaxGold 函数：这是计算黄金矿井中可收集的最大黄金量的主要函数。让我们分解一下：
  
  1. 输入：该函数接收一个二维 vector goldMine，代表黄金矿井网格，以及两个整数 n 和 m，分别代表行数和列数。
  2. 动态规划 (DP) 表：初始化一个二维 DP 表 dp[n][m]，用于存储矿井中每个单元格可收集的最大黄金量。每个条目 dp[i][j] 将保存从单元格 (i, j) 开始并向右移动时可以收集的最大黄金量。
  3. 反向迭代：算法从最后一列（最右边）到第一列（最左边）进行迭代，根据三个可能的移动方式计算每个单元格可收集的最大黄金量。
  4. 向右：移动到同一行的右侧。
  5. 右上对角线：向右上方移动（上一行）。
  6. 右下对角线：向右下方移动（下一行）。

对于每个单元格 (i, j)，算法计算这三个移动的最大值，并加上当前单元格的黄金量 (goldMine[i][j])。这三个可能的值是：

1. goldRight：通过向右移动（同一行）收集黄金。
2. goldRightUp：通过向右上移动（向上移动一行，如果不在边界外）收集黄金。
3. goldRightDown：通过向右下移动（向下移动一行，如果不在边界外）收集黄金。

为了处理边缘情况，例如在第一行无法向上移动，或者在最后一行向下移动超出边界，代码使用条件语句来避免访问无效索引。

• 最终结果：一旦 DP 表完全填充，通过选择 DP 表第一列中的最大值来找到问题的解决方案。目标是从第一列的任何一行开始，移动到最后一列。然后函数返回此最大值。
• 辅助函数 printGoldMine：此函数接收 goldMine 网格并以可读的格式打印它。它在主函数中用于在计算可收集的最大黄金量之前显示黄金矿井。
• 主函数：主 函数 是执行多个测试用例的地方，以演示解决方案如何在不同的输入上工作。提供了五个示例黄金矿井，每个都有不同的配置：
  
  1. GoldMine1 和 GoldMine2：这些是具有不同网格大小和值的简单测试用例。
  2. GoldMine3：此示例使用一个更大的黄金矿井，包含 5 行 6 列。
  3. GoldMine4：这是一个网格中所有值为零的测试用例，代表一个空的黄金矿井。
  4. GoldMine5：一个更复杂的测试用例，包含随机值，以进一步测试解决方案的健壮性。

对于每个黄金矿井，程序将打印网格并使用 getMaxGold 函数计算可收集的最大黄金量。结果显示在控制台上。

复杂度分析

时间复杂度

所提供的 C++ 解决方案在黄金矿工问题上的时间复杂度可以通过分析算法的两个主要阶段来分解：初始化和填充 DP 表。

DP 表的初始化

算法首先初始化一个 DP 表（一个二维 数组），其维度为 n x m，其中 n 是行数（黄金矿井的高度），m 是列数（黄金矿井的宽度）。初始化表包括创建一个具有 n 行 m 列的矩阵，其中每个元素最初设置为零。

此步骤的时间复杂度与表中元素的数量成正比，即 n * m。因此，DP 表初始化的时间复杂度为 O(n * m)。

填充 DP 表

初始化 DP 表后，算法会迭代黄金矿井中的每个单元格，以填充 DP 表中每个点的最大可收集黄金量。这涉及两个嵌套循环：

外层循环迭代每一列，从最右边的列开始，向最左边的列移动。这会导致 m 次迭代，其中 m 是网格中的总列数。

内层循环遍历当前列的每一行，导致每列 n 次迭代，其中 n 代表总行数。

对于每个单元格 (i, j)，算法评估最多三个可能的移动选项：

• 向右 (→)：转移到下一列的同一行。
• 右上对角线 (↗)：移动到下一列的上一行（如果不在第一行）。
• 右下对角线 (↘)：移动到下一列的下一行（如果不在最后一行）。

这些检查中的每一个都需要访问 DP 表中先前计算的值，这涉及恒定时间操作。因此，每个单元格的计算需要 O(1)，从而导致填充整个 DP 表的总时间复杂度为 O(n * m)。

由于有 n 行和 m 列，处理的总单元格数为 n * m。对于每个单元格，会执行恒定时间的运算来更新 DP 表。因此，填充 DP 表的总时间复杂度为 O(n * m)。

查找最大值

一旦 DP 表被填充，算法就需要通过检查 DP 表的第一列来找到最大可收集的黄金量。这需要遍历第一列的所有 n 行，这需要 n 次比较。因此，此最终步骤的时间复杂度为 O(n)。

空间复杂度

算法的空间复杂度由 DP 表和任何辅助存储使用的附加内存量决定。

DP 表

对空间消耗贡献最大的组件是 DP 表，这是一个 n x m 大小的二维数组。该表存储算法处理网格时每个单元格可收集的最大黄金量。表中的每个条目都代表该特定单元格基于先前计算值的最优解。此 DP 表所需的空间为 O(n * m)。

辅助变量

除了 DP 表之外，算法还使用几个整数变量，例如 goldRight、goldRightUp、goldRightDown 和 maxGold，用于在计算每个单元格的最大可收集黄金量期间存储中间结果。这些变量用于在计算最大黄金量期间保存临时值。重要的是，这些辅助 变量 所需的空间不随输入网格大小而变化。因此，这些变量的空间需求为 O(1)。

总空间复杂度由 DP 表所需的空间主导，即 O(n * m)。与此相比，辅助空间 (O(1)) 可以忽略不计。

因此，该算法的总空间复杂度为 O(n * m)。