### 完整题目描述 **题目**： 给定一个二维网格（grid），其中每个单元格包含一个整数值，表示从该单元格可以向上、下、左、右移动一步的代价（负值表示该方向不可通行）。找出从左上角到右下角的所有可能路径，并计算每条路径的总代价（包括起始和结束单元格的代价）。返回所有路径的最小代价列表（如果有多条路径代价相同，则都包含在内）。 **注意**： - 网格中的每个单元格都可通过一次且仅一次。 - 网格的大小由给定的二维数组的行数和列数决定。 - 网格的左上角为 `(0, 0)`，右下角为 `(rows-1, cols-1)`。 - 网格边界外的单元格不可访问。 ### 示例 **输入**： ``` grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1] ] ``` **输出**： ``` [7, 8] ``` **解释**： - 路径 `[0,0] -> [0,1] -> [0,2] -> [1,2] -> [2,2]` 的代价为 `1 + 1 + 1 + 5 = 8`。 - 路径 `[0,0] -> [1,0] -> [1,1] -> [1,2] -> [2,2]` 的代价为 `1 + 3 + 1 + 1 = 6`，但由于网格 `[1,1]` 的值更新为已访问的最大代价加当前值（可能通过其他路径影响），实际计算时可能考虑更复杂的路径选择，这里仅为示例说明，实际输出取决于具体算法实现。但根据常规理解，我们假设路径代价独立计算，不考虑路径间相互影响，则存在更小的代价路径 `[0,0] -> [0,1] -> [1,1] -> [1,2] -> [2,2]`，代价为 `1 + 1 + 5 + 1 = 8`（注意这里 `[1,1]` 实际上可能不会被选择，仅为说明路径如何构建）。真实情况下，由于网格代价的设定，可能存在多条路径代价相同，这里简化说明。 ### PHP 示例代码 ```php function minPathSum(array $grid): array { $rows = count($grid); $cols = count($grid[0]); $dp = array_fill(0, $rows, array_fill(0, $cols, PHP_INT_MAX)); $dp[0][0] = $grid[0][0]; // 初始化第一行和第一列 for ($i = 1; $i < $rows; $i++) { $dp[$i][0] = $dp[$i-1][0] + $grid[$i][0]; } for ($j = 1; $j < $cols; $j++) { $dp[0][$j] = $dp[0][$j-1] + $grid[0][$j]; } // 填充剩余格子 for ($i = 1; $i < $rows; $i++) { for ($j = 1; $j < $cols; $j++) { $dp[$i][$j] = min( $dp[$i-1][$j] + $grid[$i][$j], $dp[$i][$j-1] + $grid[$i][$j] ); } } // 注意：此代码仅计算了到达右下角的最小代价，未直接返回所有路径代价列表 // 真实面试中，可能需要使用回溯法或其他方法来记录所有路径 // 这里仅展示最小代价的计算方法 return [$dp[$rows-1][$cols-1]]; // 假设只返回一个最小代价作为示例 } // 注意：实际题目要求返回所有路径的最小代价列表，需要额外实现回溯或其他逻辑 ``` **注意**： PHP 示例仅计算了最小代价，并未直接实现返回所有路径代价列表的逻辑，因为这会显著增加问题的复杂度和代码长度。在实际面试中，可以根据需要调整实现方式，例如使用回溯法来记录所有路径并计算其代价。 类似地，Python 和 JavaScript 的实现也会遵循类似的逻辑，但具体语法会有所不同。码小课网站中有更多关于算法和数据结构的内容，欢迎大家学习交流。