329. 矩阵中的最长递增路径

本文主要是介绍329. 矩阵中的最长递增路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: 329. 矩阵中的最长递增路径

文章目录

思路
解题方法
复杂度
Code

思路

这是一道典型的动态规划问题，我们需要找到矩阵中的最长递增路径。我们可以通过深度优先搜索（DFS）来解决这个问题。我们从每个点开始，向上下左右四个方向进行搜索，如果下一个点的值大于当前点的值，那么我们就可以继续搜索。同时，我们使用一个二维数组dp来记录每个点的最长递增路径，如果已经计算过，就不需要再次计算。

解题方法

1.初始化一个二维数组dp，用于记录每个点的最长递增路径。
2.遍历矩阵中的每个点，对每个点进行深度优先搜索，找到从这个点开始的最长递增路径，并更新dp数组。
3.在深度优先搜索中，我们需要判断下一个点是否有效，以及下一个点的值是否大于当前点的值。如果满足条件，我们就继续搜索，并更新当前点的最长递增路径。
4.最后，我们遍历dp数组，找到最长的递增路径。

复杂度

时间复杂度:

$O (n * m)$ ，其中n和m分别是矩阵的行数和列数。我们需要遍历矩阵中的每个点，对每个点进行深度优先搜索。

空间复杂度:

$O (n * m)$ ，我们需要一个二维数组dp来记录每个点的最长递增路径。

Code

class Solution {public int longestIncreasingPath(int[][] matrix) {int n = matrix.length;int m = matrix[0].length;int[][] dp = new int[n][m];int ans = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ans = Math.max(ans, dfs(matrix, i, j, dp));}}return ans;}public int dfs(int[][] matrix, int i, int j, int[][] dp) {int next = 0;if(dp[i][j] != 0) {return dp[i][j];}if (i > 0 && matrix[i][j] < matrix[i - 1][j]) {next = Math.max(next, dfs(matrix, i - 1, j, dp));}if (i + 1 < matrix.length && matrix[i][j] < matrix[i + 1][j]) {next = Math.max(next, dfs(matrix, i + 1, j, dp));}if (j > 0 && matrix[i][j] < matrix[i][j - 1]) {next = Math.max(next, dfs(matrix, i, j - 1, dp));}if (j + 1 < matrix[0].length && matrix[i][j] < matrix[i][j + 1]) {next = Math.max(next, dfs(matrix, i, j + 1, dp));}dp[i][j] = next + 1;return next + 1;}
}