# c# Accepted Solution! DFS & DP

• public class Solution {
private int m;
private int n;
private int[,] matrix;
private int[,] dp;
public int LongestIncreasingPath(int[,] matrix)
{
this.matrix = matrix;
m = matrix.GetLength(0);
n = matrix.GetLength(1);
if ((long)m * n == 0)
return 0;
dp = new int[m, n];
int result = 1;
bool[,] visited = new bool[m, n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
result = Math.Max(result, LongestIncreasingPathHelper(visited, i, j));
}
}

``````        return result;
}
private int LongestIncreasingPathHelper(bool[,] visited, int x, int y)
{
int curr;
int result = 1;
visited[x, y] = true;
// to right(have value on right && right value isn't visited && right value > curr)
if (y < (n - 1) && !visited[x, y + 1] && matrix[x, y + 1] > matrix[x, y])
{
if(dp[x, y+1] >0)
curr = dp[x, y+1];
else
{
curr = LongestIncreasingPathHelper(visited, x, y + 1);
}

result = Math.Max(result, curr+1);
}

// to left
if (y > 0 && !visited[x, y - 1] && matrix[x, y - 1] > matrix[x, y])
{
if (dp[x, y - 1] > 0)
curr = dp[x, y - 1];
else
{
curr = LongestIncreasingPathHelper(visited, x, y - 1);
}

result = Math.Max(result, curr+1);
}

// to down
if (x < (m-1) && !visited[x+1, y] && matrix[x+1, y] > matrix[x, y])
{
if (dp[x+1, y] > 0)
curr = dp[x+1, y];
else
{
curr = LongestIncreasingPathHelper(visited, x+1, y);
}

result = Math.Max(result, curr+1);
}

// to up
if (x > 0 && !visited[x - 1, y] && matrix[x - 1, y] > matrix[x, y])
{
if (dp[x - 1, y] > 0)
curr = dp[x - 1, y];
else
{
curr = LongestIncreasingPathHelper(visited, x - 1, y);
}

result = Math.Max(result, curr+1);
}

visited[x, y] = false;
dp[x,y] = result;
return result;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.