题目描述

给定一个m x n的网格，网格中的每个单元格都有一个整数。从左上角开始，你只能向右或向下移动到相邻的单元格。你的任务是找到从左上角到右下角的最小路径和。

示例：

网格如下：

[
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]

从左上角到右下角的最小路径和为 7。

注意：

• 你只能向右或向下移动。
• 网格中至少包含一个单元格。
• 网格中的所有值都是非负整数。

PHP 示例代码

function minPathSum($grid) {
    $m = count($grid);
    $n = count($grid[0]);

    // 初始化第一行和第一列
    for ($i = 0; $i < $m; $i++) {
        for ($j = 0; $j < $n; $j++) {
            if ($i == 0 && $j > 0) {
                $grid[$i][$j] += $grid[$i][$j - 1];
            } elseif ($j == 0 && $i > 0) {
                $grid[$i][$j] += $grid[$i - 1][$j];
            } elseif ($i > 0 && $j > 0) {
                $grid[$i][$j] += min($grid[$i - 1][$j], $grid[$i][$j - 1]);
            }
        }
    }

    return $grid[$m - 1][$n - 1];
}

// 示例用法
$grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
];
echo minPathSum($grid); // 输出 7

Python 示例代码

def minPathSum(grid):
    m, n = len(grid), len(grid[0])

    # 初始化第一行和第一列
    for i in range(1, m):
        grid[i][0] += grid[i-1][0]
    for j in range(1, n):
        grid[0][j] += grid[0][j-1]

    # 动态规划计算最小路径和
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])

    return grid[m-1][n-1]

# 示例用法
grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
print(minPathSum(grid))  # 输出 7

JavaScript 示例代码

function minPathSum(grid) {
    const m = grid.length;
    const n = grid[0].length;

    // 初始化第一行和第一列
    for (let i = 1; i < m; i++) {
        grid[i][0] += grid[i-1][0];
    }
    for (let j = 1; j < n; j++) {
        grid[0][j] += grid[0][j-1];
    }

    // 动态规划计算最小路径和
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
        }
    }

    return grid[m-1][n-1];
}

// 示例用法
const grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
];
console.log(minPathSum(grid)); // 输出 7

这些示例代码均采用了动态规划的思想，通过原地修改网格中的值来避免额外的空间复杂度，最终返回从左上角到右下角的最小路径和。