题解

题面描述

给定一个包含非负整数的 $m\times n$ 网格 $grid$ ，要求找出一条从左上角到右下角的路径，使得路径上所有数字的和最小。每一步只能向右或者向下移动。

思路

本题可以使用动态规划进行求解。令 $dp[i][j]$ 表示从起点到 $grid[i][j]$ 的最小路径和，则状态转移公式为

$dp[i][j]$ = $\min(dp[i-1][j],\ dp[i][j-1]) + grid[i][j]$

边界条件为：

• $dp[0][0]=grid[0][0]$
• 第一列：$dp[i][0]=dp[i-1][0]+grid[i][0]$
• 第一行：$dp[0][j]=dp[0][j-1]+grid[0][j]$

最后答案为 $dp[m-1][n-1]$。

代码分析

• 状态定义： 使用二维数组 $dp$ 保存每个位置的最小路径和。
• 状态转移： 对于位置 $grid[i][j]$，只能从上面 $grid[i-1][j]$ 或左边 $grid[i][j-1]$ 到达，因此取两者中的较小值再加上当前位置的值。
• 边界处理： 第一行和第一列的处理需要单独初始化。
• 时间复杂度： $O(m\times n)$，空间复杂度同样为 $O(m\times n)$。

C++

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 使用 Solution 类包装功能函数，符合 LeetCode 风格
class Solution {
public:
    // 求解最小路径和的函数
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();          // m 行
        int n = grid[0].size();       // n 列
        vector<vector<int>> dp(m, 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];
        }
        // 动态规划状态转移
        for (int i = 1; i < m; i++) {
            for (int 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];  // 返回终点的最小路径和
    }
};

int main() {
    vector<vector<int>> grid;  // 存放输入的网格
    string line;
    // 使用 getline 读取每一行输入，适应 ACM 模式
    while(getline(cin, line)){
        if(line.empty()) continue;
        stringstream ss(line);
        vector<int> row;
        int x;
        // 解析一行中的数字
        while(ss >> x){
            row.push_back(x);
        }
        if(!row.empty()){
            grid.push_back(row);
        }
    }
    if(grid.empty()) return 0;
    Solution sol;
    // 输出结果
    cout << sol.minPathSum(grid) << endl;
    return 0;
}

Python

# 定义 Solution 类，符合 LeetCode 风格
class Solution:
    def minPathSum(self, grid: list) -> int:
        m = len(grid)      # m 行
        n = len(grid[0])   # n 列
        # 初始化动态规划数组 dp
        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]
        # 状态转移
        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[m-1][n-1]  # 返回终点的最小路径和

if __name__ == '__main__':
    import sys
    grid = []
    # 逐行读取输入数据
    for line in sys.stdin:
        if line.strip() == '':
            continue
        # 解析每行的数字
        row = list(map(int, line.split()))
        grid.append(row)
    if grid:
        sol = Solution()
        # 输出结果
        print(sol.minPathSum(grid))

Java

import java.util.*;
import java.io.*;

public class Main {
    // 定义 Solution 类，符合 LeetCode 风格
    static class Solution {
        public int minPathSum(int[][] grid) {
            int m = grid.length;        // m 行
            int n = grid[0].length;     // n 列
            int[][] dp = new int[m][n]; // 定义动态规划数组 dp
            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];
            }
            // 状态转移
            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) throws IOException {
        // 使用 BufferedReader 读取输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        ArrayList<int[]> gridList = new ArrayList<>();
        // 逐行读取输入数据
        while((line = br.readLine()) != null && line.length() != 0){
            String[] parts = line.trim().split("\\s+");
            int[] row = new int[parts.length];
            // 解析每行中的数字
            for (int i = 0; i < parts.length; i++){
                row[i] = Integer.parseInt(parts[i]);
            }
            gridList.add(row);
        }
        if(gridList.size() == 0) return;
        int m = gridList.size();            // m 行
        int n = gridList.get(0).length;       // n 列
        int[][] grid = new int[m][n];
        // 构造二维数组
        for(int i = 0; i < m; i++){
            grid[i] = gridList.get(i);
        }
        Solution sol = new Solution();
        // 输出结果
        System.out.println(sol.minPathSum(grid));
    }
}

题目内容

给定一个包含非负整数的 $m× n$网格 $grid$ ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明:**每次只能向下或者向右移动一步。

输入描述

输入一个$m× n$网格

输出描述

最小路径和

样例1

输入

1 3 1
1 5 1
4 2 1

输出

7

说明

因为路径 1→3→1→1→1 的总和最小。

样例2

输入

1 2 3
4 5 6

输出

12

提示

• $m == grid.length$
• $n == grid[i].length$
• $1 <= m, n <= 200$
• $0 <= grid[i][j] <= 200$