在矩阵最短路径问题中，我们通常假设只能向右或向下移动，目标是找到从左上角到右下角的最小路径和，同时记录下这条路径的具体走向。动态规划的核心是把大问题拆成子问题，用数组存储每个位置的最小路径代价，再通过回溯数组得到完整路径。
核心思路说明
首先定义一个二维数组dp，其中dp[i][j]表示从左上角(0,0)到位置(i,j)的最小路径和。状态转移逻辑为：如果当前位置是左上角起点，dp[0][0]等于矩阵对应位置的值；如果是第一行的位置，只能从左边过来，所以dp[0][j] = dp[0][j-1] + matrix[0][j]；如果是第一列的位置，只能从上边过来，所以dp[i][0] = dp[i-1][0] + matrix[i][0]；其他位置则取左边和上边的最小值加上当前位置的值，即dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]。
为了记录路径，我们还需要一个二维数组prev，prev[i][j]存储到达(i,j)的上一个位置的坐标，这样在计算完所有dp值后，从右下角开始回溯prev数组，就能得到完整的最短路径。
完整代码实现
以下是完整的Java实现代码，包含路径计算和路径回溯两部分：
public class MatrixShortestPath {
public static void main(String[] args) {
// 定义示例矩阵
int[][] matrix = {
{1, 3, 1},
{1, 5, 1},
{4, 2, 1}
};
int rows = matrix.length;
int cols = matrix[0].length;
// dp数组存储到每个位置的最小路径和
int[][] dp = new int[rows][cols];
// prev数组存储每个位置的前驱坐标，0表示来自上边，1表示来自左边
int[][] prev = new int[rows][cols];
// 初始化起点
dp[0][0] = matrix[0][0];
prev[0][0] = -1; // 起点没有前驱
// 初始化第一列，只能从上边过来
for (int i = 1; i < rows; i++) {
dp[i][0] = dp[i-1][0] + matrix[i][0];
prev[i][0] = 0; // 0代表前驱是上边的位置
}
// 初始化第一行，只能从左边过来
for (int j = 1; j < cols; j++) {
dp[0][j] = dp[0][j-1] + matrix[0][j];
prev[0][j] = 1; // 1代表前驱是左边的位置
}
// 填充剩余dp数组和prev数组
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
// 比较上边和左边的路径和
if (dp[i-1][j] < dp[i][j-1]) {
dp[i][j] = dp[i-1][j] + matrix[i][j];
prev[i][j] = 0; // 来自上边
} else {
dp[i][j] = dp[i][j-1] + matrix[i][j];
prev[i][j] = 1; // 来自左边
}
}
}
// 输出最小路径和
System.out.println("矩阵最短路径和为：" + dp[rows-1][cols-1]);
// 回溯prev数组得到路径
StringBuilder path = new StringBuilder();
int i = rows - 1;
int j = cols - 1;
// 从终点回溯到起点
while (i != 0 || j != 0) {
if (prev[i][j] == 0) {
// 来自上边，当前位置加入路径，移动到上边位置
path.insert(0, " -> (" + i + "," + j + ")");
i = i - 1;
} else if (prev[i][j] == 1) {
// 来自左边，当前位置加入路径，移动到左边位置
path.insert(0, " -> (" + i + "," + j + ")");
j = j - 1;
}
}
// 加入起点
path.insert(0, "(0,0)");
System.out.println("最短路径为：" + path.toString());
}
}
代码运行结果说明
以上示例矩阵的运行结果为：最短路径和为7，路径为(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)。可以看到，通过dp数组计算出了每个位置的最小路径和，再通过prev数组回溯得到了完整的路径走向，整个过程仅使用了数组作为存储结构，没有额外的复杂数据结构，实现逻辑清晰易懂。
注意事项
- 矩阵的行数和列数需要提前判断，避免空矩阵导致的数组越界问题。
prev数组的标记规则需要统一，避免回溯时出现逻辑错误。- 如果矩阵允许其他移动方向，只需要调整状态转移的逻辑和
prev数组的存储内容即可，核心思路不变。