小学生都能看懂的题解 | #矩阵最长递增路径#

问题描述：

假设你在一个大迷宫里，迷宫是由很多小格子组成的。每个格子上有一个数字，你要找到一条最长的路，使得你走过的数字是从小到大递增的。你可以向上、下、左、右四个方向走，但不能走出迷宫，也不能重复走过同一个格子。

目标：

找到这条最长的递增路径，并告诉别人这条路有多长。

解决方案：

我们可以把这个迷宫想象成一个游戏地图，我们需要找到最长的递增路径。为了做到这一点，我们可以做以下几个步骤：

1. 记录每个格子的最大路径长度：我们需要一个笔记本（二维数组 dp），记录每个格子能走到的最长递增路径的长度。
2. 探索每个格子：对于每个格子，我们要看看它周围的四个邻居（上、下、左、右），如果邻居的数字比当前格子的数字大，那么我们就可以继续探索。
3. 记住已经探索过的路径：为了避免重复计算，我们需要记住每个格子的最长路径长度。

代码实现：

import java.util.Arrays;

public class LongestIncreasingPath {

    private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    /**
     * 寻找矩阵中最长递增路径的长度
     * @param matrix 输入矩阵
     * @return 最长递增路径的长度
     */
    public int solve(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols]; // 初始化一个二维数组，记录每个格子的最大路径长度

        // 记录最大路径长度
        int maxLength = 0;

        // 遍历每个格子
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                maxLength = Math.max(maxLength, dfs(matrix, dp, row, col, rows, cols));
            }
        }

        return maxLength;
    }

    /**
     * 深度优先搜索
     * @param matrix 输入矩阵
     * @param dp 动态规划数组
     * @param row 当前行
     * @param col 当前列
     * @param rows 矩阵行数
     * @param cols 矩阵列数
     * @return 当前格子的最长递增路径长度
     */
    private int dfs(int[][] matrix, int[][] dp, int row, int col, int rows, int cols) {
        if (dp[row][col] != 0) {
            return dp[row][col]; // 如果已经计算过，直接返回
        }

        int maxLength = 1; // 至少包括自己
        for (int[] direction : DIRECTIONS) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];

            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && matrix[newRow][newCol] > matrix[row][col]) {
                maxLength = Math.max(maxLength, 1 + dfs(matrix, dp, newRow, newCol, rows, cols));
            }
        }

        dp[row][col] = maxLength; // 记录当前格子的最长路径长度
        return maxLength;
    }


}

解释：

1. 初始化状态：我们创建一个 dp 数组来记录每个格子能走到的最长递增路径的长度。
2. 遍历每个格子：我们遍历矩阵中的每个格子，对每个格子调用 dfs 方法来计算其最长递增路径长度。
3. 深度优先搜索：对于每个格子，我们查看其四个方向的邻居，如果邻居的数字大于当前格子的数字，我们继续深入探索邻居。
4. 记忆化搜索：为了避免重复计算，我们在 dfs 方法中记录已经计算过的格子的最长路径长度。

示例运行结果：

• 输入：[[1, 2, 3], [4, 5, 6], [7, 8, 9]]输出：5
• 输入：[[1, 2], [4, 3]]输出：4

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。