遍历矩阵行收集最大硬币问题是否存在O(mn)时间复杂度算法

该问题存在时间复杂度为O(mn)的求解算法，基于动态规划结合前缀/后缀最大值优化实现。

基础动态规划思路 #

我们先定义dp[i][j]为走到第i行第j列时，可收集的最大硬币总数。对应的暴力转移方程为：

dp[i][j] = (max_{k=0}^{n-1} (dp[i-1][k] - |j - k|)) + grid[i][j]

其中边界条件为第一行的dp[0][j] = grid[0][j]（第一行任选列，没有移动成本）。
如果直接暴力枚举每个位置j对应的所有k计算最大值，总时间复杂度为O(mn²)，不符合效率要求。

O(mn)优化方案 #

我们可以通过拆分绝对值，把需要全局求最大值的项拆分为可通过前缀、后缀最大值快速计算的形式：

• 当k ≤ j时，|j - k| = j - k，对应最大值项可改写为 max(dp[i-1][k] + k) - j
• 当k ≥ j时，|j - k| = k - j，对应最大值项可改写为 max(dp[i-1][k] - k) + j

具体优化步骤为：

• 从左到右遍历上一行的dp结果，维护前缀最大值数组left_max，其中left_max[j]表示上一行0到j列范围内dp[i-1][k] + k的最大值
• 从右到左遍历上一行的dp结果，维护后缀最大值数组right_max，其中right_max[j]表示上一行j到n-1列范围内dp[i-1][k] - k的最大值
• 对当前行的每个位置j，直接通过dp[i][j] = max(left_max[j] - j, right_max[j] + j) + grid[i][j]计算当前dp值

每一行的处理仅需要3次O(n)的遍历，因此总时间复杂度为O(mn)。

补充优化 #

该算法的空间复杂度还可以进一步优化到O(n)：不需要存储完整的二维dp数组，仅需要保留上一行的dp计算结果即可。

内容的提问来源于stack exchange，提问作者jayx95