成本有界的二维数组最大利润和路径求解问题

问题重述 #

给定两个n × n 二维矩阵：

• 成本矩阵 cost：cost[i][j] 代表走到坐标(i,j)需要消耗的成本
• 利润矩阵 profit：profit[i][j] 代表走到坐标(i,j)可以获得的利润
  要求寻找从左上角(0,0)到右下角(n-1,n-1)的路径，仅允许向右或向下移动，满足路径总成本之和不超过给定阈值C，求所有符合条件的路径中总利润的最大值，数据约束为n ≤ 100。

核心解法：动态规划 #

这是典型的带约束的路径最优问题，动态规划是最适配的解法，针对不同的阈值C范围可以选择两种状态定义：

方案1：以成本为状态维度（适合C ≤ 1e4的场景） #

• 状态定义：dp[i][j][k] 表示走到(i,j)位置时，累计成本刚好为k的前提下，能获得的最大利润。
• 状态转移：仅能从上方(i-1,j)或左方(i,j-1)转移而来：

  dp[i][j][k] = max(
      dp[i-1][j][k - cost[i][j]], 
      dp[i][j-1][k - cost[i][j]]
  ) + profit[i][j]
  

• 边界初始化：起点状态 dp[0][0][cost[0][0]] = profit[0][0]，其余所有状态初始化为负无穷（代表不可达）。
• 结果计算：遍历所有k ≤ C的dp[n-1][n-1][k]，取最大值即为所求。
• 空间优化：可以用滚动二维数组替代三维数组，每次仅保留当前行/当前层的状态，空间复杂度从O(n²C)降到O(nC)。

方案2：以利润为状态维度（适合总利润上限较低的场景） #

如果阈值C过大（比如超过1e5），方案1的时间复杂度会过高，可以反过来定义状态：

• 状态定义：dp[i][j][k] 表示走到(i,j)位置时，累计利润刚好为k的前提下，消耗的最小成本。
• 状态转移逻辑和方案1一致，最终找最大的k满足dp[n-1][n-1][k] ≤ C即可。

复杂度说明 #

当n=100、C=1e3时，方案1的时间复杂度为O(n²C) = 1e7，属于常规算力可以轻松处理的范围，完全符合题目约束要求。

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