Here is the link.
C# | DFS + memorization | Editorial
Intuition
Approach
Complexity
- Time complexity:
- Space complexity:
Code
public class Solution {
private static int[][] dirs = new int[][] {new int[]{0, 1}, new int[]{1, 0}, new int[]{0, -1}, new int[]{-1, 0}};
private int m, n;
public int LongestIncreasingPath(int[][] matrix)
{
if (matrix.Length == 0){
return 0;
}
m = matrix.Length;
n = matrix[0].Length;
var cache = new int[m][];
for (int row = 0; row < m; row++)
{
cache[row] = new int[n];
}
int ans = 0;
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
ans = Math.Max(ans, dfs(matrix, i, j, cache));
}
}
return ans;
}
/// <summary>
/// What I learned on Nov. 6, 2023:
/// 1. There is no loop - increasing order - no need to check visited or not
/// 2. Every node will be visited once - save into cache
/// 3. Every edge will be checked - each node has four neighbors - 4 * rows * columns
/// 4. Understand how DFS works for this problem
/// </summary>
/// <param name="matrix"></param>
/// <param name="i"></param>
/// <param name="j"></param>
/// <param name="cache"></param>
/// <returns></returns>
private int dfs(int[][] matrix, int i, int j, int[][] cache) {
if (cache[i][j] != 0)
{
return cache[i][j];
}
foreach (var d in dirs)
{
var x = i + d[0];
var y = j + d[1];
if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j])
{
cache[i][j] = Math.Max(cache[i][j], dfs(matrix, x, y, cache));
}
}
return ++cache[i][j];
}
}