用parent数组记录路径来源可实现最短路径追溯：初始化parenti为-1，转移时若dpi-1
在 Java 中，用数组实现动态规划（DP）记录路径并求矩阵最短路径，核心是：用一个二维 DP 数组存最小路径和，再用另一个二维数组（或通过推导规则）反向还原路径。关键不在于“动态规划有多难”，而在于“怎么让路径可追溯”。下面分三步讲清楚。
1. 定义状态与初始化 DP 数组
假设给定一个 m × n 的非负整数矩阵 grid，只能向右或向下移动，求从左上角 (0,0) 到右下角 (m-1,n-1) 的最小路径和，并记录具体经过的坐标。
定义 dp[i][j] 表示到达 (i,j) 的最小路径和：
dp[0][0] = grid[0][0]- 第一行只能从左来：
dp[0][j] = dp[0][j-1] + grid[0][j] - 第一列只能从上来：
dp[i][0] = dp[i-1][0] + grid[i][0] - 其余位置：
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
2. 用 parent 数组记录路径来源
只算出最小和还不够，要还原路径，需知道每个位置是从上方还是左方来的。推荐用一个二维字符串数组或 int 数组标记方向：
- 定义
parent[i][j]，值为"U"（来自上方）、"L"（来自左方），或用数字如0=up, 1=left - 初始化边界无来源（可设为
-1或空） - 转移时同步更新：
if (dp[i-1][j] dp[i][j] = dp[i-1][j] + grid[i][j];
parent[i][j] = 0; // 来自上方
} else {
dp[i][j] = dp[i][j-1] + grid[i][j];
parent[i][j] = 1; // 来自左方
}
3. 反向构建路径列表
从终点 (m-1, n-1) 出发，根据 parent 数组不断回退，直到回到起点，再将路径反转即可得到正向坐标序列：
- 用
ArrayList<int></int>存路径点，先 add 终点 - 设
i = m-1, j = n-1，循环直到i==0 && j==0 - 若
parent[i][j] == 0，则上一步是(i-1, j)；若为1，则是(i, j-1) - 最后调用
Collections.reverse(path)
例如矩阵 [[1,3,1],[1,5,1],[4,2,1]]，最短路径和为 7，路径为 [(0,0)→(1,0)→(1,1)→(1,2)→(2,2)]，实际还原过程清晰可控。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
