每日一题（8） 求解矩阵最小路径和问题

给定一个m行n列的矩阵，从左上角开始每次只能向右或者向下移动，最后到达右下角的位置，路径上的所有数字累加起来作为这条路径的路径和。求所有路径和中最小路径和。

输入格式:

首先输入行数m及列数n，接下来输入m行，每行n个数。

输出格式:

输出第一行为最小路径（假定测试数据中的最小路径唯一），第2行为最小路径和。

输入样例1:

4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0

输出样例1:

1 3 1 0 6 1 0 
12

问题分析

这是一个典型的路径规划问题，可以使用动态规划来解决。我们需要找到从矩阵左上角到右下角的最小路径和，并记录下这条路径。

在每个点上，我们只能向右或向下移动，因此到达位置 (i, j) 的路径只能来自于位置 (i-1, j)（上方）或位置 (i, j-1)（左方）。我们选择这两个来源中路径和较小的那个，然后加上当前位置的值，即可得到到达 (i, j) 的最小路径和。

解题思路

动态规划解法

我们定义：

• dp[i][j] 表示从起点 (0, 0) 到达位置 (i, j) 的最小路径和

• pace[i][j] 用于记录到达位置 (i, j) 的前一步是从哪个方向来的（0表示从上方，1表示从左方）

状态转移方程为：

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + num[i][j]

边界条件：

• dp[0][0] = num[0][0]

• 对于第一行：dp[0][j] = dp[0][j-1] + num[0][j]（只能从左侧来）

• 对于第一列：dp[i][0] = dp[i-1][0] + num[i][0]（只能从上方来）

计算完 dp 数组后，dp[m-1][n-1] 就是我们要求的最小路径和。

为了重建最小路径，我们使用 pace 数组记录每一步的选择，然后用栈存储从终点回溯到起点的路径，最后输出即可得到完整路径。

代码实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[][] num = new int[m][n];
        for(int i=0;i<m;i++){
            st = new StringTokenizer(bf.readLine());
            for(int j=0;j<n;j++){
                num[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] dp = new int[m][n];
        int[][] pace = new int[m][n];
        dp[0][0] = num[0][0];
        //初始化第一行和第一列
        for(int i=1;i<m;i++){
            dp[i][0] = num[i][0] + dp[i-1][0];
            pace[i][0] = 0;
        }
        for(int i=1;i<n;i++){
            dp[0][i] = num[0][i] + dp[0][i-1];
            pace[0][i] = 1;
        }

        //状态转移方程
        //dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + num[i][j];
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(dp[i-1][j]<dp[i][j-1]){
                    dp[i][j] = dp[i-1][j] + num[i][j];
                    pace[i][j] = 0;
                }
                else{
                    dp[i][j] = dp[i][j-1] + num[i][j];
                    pace[i][j] = 1;
                }
            }
        }

        //逆推路径
        Stack<Integer> temp = new Stack<>();
        int i=m-1,j=n-1;
        while (i>0||j>0){
            temp.push(num[i][j]);
            if(pace[i][j]==0) i--;
            else j--;
        }
        temp.push(num[0][0]);

        while (!temp.isEmpty()){
            System.out.print(temp.pop()+" ");
        }
        System.out.println();
        System.out.println(dp[m-1][n-1]);
    }
}

这种方法的时间复杂度为 O(m×n)，空间复杂度也为 O(m×n)，其中 m 和 n 分别是矩阵的行数和列数。