m×n矩阵中仅允许右/向下移动的最低成本路径求解算法问询

当然有对应的算法，最经典且高效的解法就是动态规划（Dynamic Programming），完全适配你这个“仅向右/向下移动找最低成本路径”的场景，下面我一步步拆解：

这个问题的本质是无后效性的子问题最优解叠加——每个位置的最低成本，只依赖于它上方或左方位置的最低成本，用动态规划来解决再合适不过。

具体实现步骤 #

我们先定义dp[i][j]表示从矩阵左上角a[0][0]（这里用0索引举例）到a[i][j]的最低移动成本，然后分三步填充这个DP表：

1. 边界初始化

   • 第一行：只能从左边的格子依次向右移动，所以每个位置的成本是左边所有格子成本的累加：dp[0][j] = dp[0][j-1] + a[0][j]
   • 第一列：只能从上方的格子依次向下移动，所以每个位置的成本是上方所有格子成本的累加：dp[i][0] = dp[i-1][0] + a[i][0]

2. 填充DP表主体
   对于矩阵中除第一行、第一列外的任意位置(i,j)，只能从上方或左方过来，我们取这两个方向里成本更低的那个，加上当前格子的成本，就是到(i,j)的最低成本：

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

3. 结果获取
   最终矩阵右下角的dp[m-1][n-1]就是从a[1,1]到a[m,n]的最低成本。

用你的例子验证 #

拿你给出的3×3矩阵（转化为0索引）：

[
 [10, 5, 6],
 [2, 4, 7],
 [2, 2, 3]
]

按照步骤计算DP表：

• 第一行：dp[0][0]=10，dp[0][1]=10+5=15，dp[0][2]=15+6=21
• 第一列：dp[1][0]=10+2=12，dp[2][0]=12+2=14
• 中间位置：
  • dp[1][1] = min(15,12) +4 = 16
  • dp[1][2] = min(21,16) +7 =23
  • dp[2][1] = min(16,14) +2 =16
  • dp[2][2] = min(23,16) +3 =19
    正好和你给出的最低成本19一致，完美匹配！

上面的方法用了一个和原矩阵一样大的DP表，空间复杂度是O(mn)，但我们可以进一步优化：
因为计算dp[i][j]时，只需要上一行的当前列值和当前行的前一列值，所以可以用一维数组代替二维数组，把空间复杂度降到O(min(m,n))：

1. 初始化一个长度为n的一维数组dp，先填充第一行的成本：dp[j] = dp[j-1] + a[0][j]
2. 遍历从第二行开始的每一行：
   • 先更新当前行的第一个元素：dp[0] += a[i][0]
   • 然后从左到右遍历当前行的其他元素：dp[j] = min(dp[j], dp[j-1]) + a[i][j]
3. 最终dp[n-1]就是最低成本。

如果允许修改原矩阵，甚至可以直接在原矩阵上更新，完全不需要额外空间，空间复杂度降到O(1)，只需要把原矩阵的元素替换成到该位置的最低成本即可。

不管是基础版还是优化版，时间复杂度都是O(mn)——因为每个矩阵元素都只被访问和计算一次，这已经是这个问题的最优时间复杂度了，毕竟你至少得遍历每个元素一次才能得到总成本。

内容的提问来源于stack exchange，提问作者MessitÖzil