完整题目描述

题目： 给定一个二维网格（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 示例代码

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 的实现也会遵循类似的逻辑，但具体语法会有所不同。码小课网站中有更多关于算法和数据结构的内容，欢迎大家学习交流。