最小路径和

题目要求

设计一个算法，用于寻找一条从二维网格的左上角到右下角的路径，该路径上的数字之和最小。网格中包含的是非负整数，且在移动时只能向下或向右移动一步。

解题思路

这个问题是一个典型的动态规划问题。动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。

步骤一：定义状态

首先定义一个二维数组 dp，其中 dp[i][j] 表示从左上角走到网格中的点 (i, j) 时，能够获得的最小路径和。

步骤二：状态转移方程

对于网格中的每一个点，有两种方式到达它：从左边的格子向右走一步，或者从上面的格子向下走一步。因此，到达点 (i, j) 的最小路径和就是从 (i-1, j) 和 (i, j-1) 中选择一个路径和较小的，再加上当前点的值 grid[i][j]。

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

步骤三：初始化边界条件

动态规划的边界条件是算法的起点。在这个问题中，边界条件是 dp 数组的第一行和第一列。

对于第一行 dp[0][j]，它只能从左边的格子向右走到达，因此它的值是从 (0, 0) 到 (0, j) 的路径和。
对于第一列 dp[i][0]，它只能从上面的格子向下走到达，因此它的值是从 (0, 0) 到 (i, 0) 的路径和。

步骤四：填充 dp 数组

按照从上到下，从左到右的顺序，依次计算 dp 数组中每个点的值。每个点的值依赖于它上方和左方的点的值，这样可以保证每个点的值在计算时它依赖的值都已经计算过了。

步骤五：返回结果

最后，dp 数组的最右下角的值 dp[m-1][n-1] 就是从左上角到右下角的最小路径和。

通过这个动态规划的方法，我们可以有效地解决这个问题，时间复杂度和空间复杂度通常都是 O(m*n)，其中 m 和 n 分别是网格的行数和列数。

Golang 版本

package main

import (
	"fmt"
	"math"
)

func minPathSum(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}

	m, n := len(grid), len(grid[0])
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	// 初始化边界条件
	dp[0][0] = grid[0][0]
	for i := 1; i < m; i++ {
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}
	for j := 1; j < n; j++ {
		dp[0][j] = dp[0][j-1] + grid[0][j]
	}

	// 填充 dp 数组
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
		}
	}

	// 返回结果
	return dp[m-1][n-1]
}

// min 返回两个整数中较小的一个
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	grid := [][]int{
		{1, 3, 1},
		{1, 5, 1},
		{4, 2, 1},
	}
	fmt.Println(minPathSum(grid)) // 输出应为 7
}

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

int minPathSum(std::vector<std::vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) {
        return 0;
    }

    int m = grid.size(), n = grid[0].size();
    std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));

    // 初始化边界条件
    dp[0][0] = grid[0][0];
    for (int i = 1; i < m; ++i) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for (int j = 1; j < n; ++j) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    // 填充 dp 数组
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }

    // 返回结果
    return dp[m - 1][n - 1];
}

int main() {
    std::vector<std::vector<int>> grid = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };
    std::cout << minPathSum(grid) << std::endl; // 输出应为 7
    return 0;
}

Python 版本

def minPathSum(grid):
    if not grid or not grid[0]:
        return 0

    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]

    # 初始化边界条件
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]

    # 填充 dp 数组
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

    # 返回结果
    return dp[-1][-1]

# 测试代码
grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
print(minPathSum(grid))  # 输出应为 7

Java 版本

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];

        // 初始化边界条件
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        // 填充 dp 数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        // 返回结果
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] grid = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };
        System.out.println(solution.minPathSum(grid)); // 输出应为 7
    }
}

Rust 版本

fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut dp = vec![vec![0; n]; m];

    // 初始化边界条件
    dp[0][0] = grid[0][0];
    for i in 1..m {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for j in 1..n {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    // 填充 dp 数组
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = i32::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }

    // 返回结果
    dp[m - 1][n - 1]
}

fn main() {
    let grid = vec![
        vec![1, 3, 1],
        vec![1, 5, 1],
        vec![4, 2, 1],
    ];
    println!("{}", min_path_sum(grid)); // 输出应为 7
}

总结

上述解法采用了动态规划的方法来解决最小路径和问题。这个问题的核心是找到从矩阵的左上角到右下角的最小路径和。解决方案遵循以下步骤：

定义状态： 创建一个二维数组 dp，其中 dp[i][j] 表示从左上角 (0, 0) 到达 (i, j) 的最小路径和。
初始化状态：
- 初始化 dp[0][0] 为 grid[0][0]，因为这是起点。
- 初始化第一行和第一列的 dp 值，因为第一行只能从左边走到右边，第一列只能从上面走到下面。
状态转移方程： 对于 dp 数组中的其他元素，计算到达每个点的最小路径和。这是通过取其上方和左方的两个邻居的最小值并加上当前格子的值来实现的，即 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
计算结果： 按照从上到下，从左到右的顺序，依次计算 dp 数组中每个点的值，直到填充完整个 dp 数组。
返回结果： 最后，dp[m-1][n-1]（其中 m 和 n 分别是矩阵的行数和列数）就是从左上角到右下角的最小路径和。

这种方法的时间复杂度和空间复杂度都是 O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。通过这种方式，我们可以有效地解决问题，而不需要递归或者复杂的算法。

hot-100