PHP 数组最小路径和算法实现

最小路径和为右下角的最小累计值；使用一维dp数组，初始化第一行累加，后续每行按dp[j] = gridi + min(dp[j], dp[j-1])更新，最终dp[n-1]即结果。

php 中实现“数组最小路径和”通常指在二维数组（如矩阵）中，从左上角出发，每次只能向右或向下移动，到达右下角的最小路径和。这不是 PHP 特有算法，而是经典动态规划问题，但可用 PHP 清晰表达。

理解问题与状态定义

给定一个 m × n 的非负整数二维数组 $grid，起点为 $grid[0][0]，终点为 $grid[m-1][n-1]，每步只能向右或向下走一格，求所有可行路径中数字总和最小的一条。

核心思路：到达位置 (i, j) 的最小路径和，只依赖于上方 (i-1, j) 和左方 (i, j-1) 的最小路径和。

状态转移方程：
$dp[i][j] = $grid[i][j] + min($dp[i-1][j], $dp[i][j-1])

空间优化的 PHP 实现（推荐）

无需额外二维数组，直接在原数组上更新，或使用一维数组降低空间复杂度至 O(n)：

立即学习“PHP免费学习笔记（深入）”；

• 初始化一维数组 $dp 长度为列数 count($grid[0])
• 第一行单独处理：每个位置只能从左来，累加即可
• 从第二行开始，每行遍历各列：当前值 = 当前网格值 + min(上方 dp 值, 左侧 dp 值)
• 最终 $dp[n-1] 即为答案

示例代码：

function minPathSum($grid) {     if (empty($grid) || empty($grid[0])) return 0;     $m = count($grid);     $n = count($grid[0]);     $dp = array_fill(0, $n, 0);          // 初始化第一行     $dp[0] = $grid[0][0];     for ($j = 1; $j < $n; $j++) {         $dp[$j] = $dp[$j-1] + $grid[0][$j];     }          // 逐行更新     for ($i = 1; $i < $m; $i++) {         $dp[0] += $grid[$i][0]; // 第一列只能从上方来         for ($j = 1; $j < $n; $j++) {             $dp[$j] = $grid[$i][$j] + min($dp[$j], $dp[$j-1]);         }     }          return $dp[$n-1]; }

边界情况与注意事项

• 输入为空数组或某行为空时需提前返回 0，避免索引错误
• 单行或单列数组是合法输入：此时路径唯一，直接求和即可
• PHP 中数组下标从 0 开始，注意 $grid[$i][$j] 的合法性判断（尤其在调试时可加 isset 检查）
• 若需返回具体路径而非仅和值，需额外维护方向数组或回溯，复杂度上升

测试用例验证

例如输入：
[[1,3,1],[1,5,1],[4,2,1]]
期望输出：7（路径：1→3→1→1→1）

调用 minPathSum($grid) 应正确返回 7。建议用几个小规模矩阵（1×1、1×4、3×1、2×2）交叉验证逻辑鲁棒性。