# A memoization approach in C++

• I was wondering if the contributor of the question is from USC. Anyway, here is my c++ solution, dfs + memoization.

``````class Solution
{
public:
int longestIncreasingPath(vector<vector<int>>& matrix)
{
if (matrix.empty() || matrix[0].empty()) return 0;
vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), -1));

int res = 0;
for (int i = 0; i < matrix.size(); ++i)
for (int j = 0; j < matrix[0].size(); ++j)
res = max(res, dfs(matrix, i, j, dp, nullptr));

return res;
}

private:
int dfs(vector<vector<int>> &matrix, int r, int c, vector<vector<int>> &dp, int *last)
{
if (r < 0 || r >= matrix.size() || c < 0 || c >= matrix[0].size()) return 0;
if (last && *last <= matrix[r][c]) return 0;
if (dp[r][c] > 0) return dp[r][c];

dp[r][c] = 1;
int res = 0;
res = max(res, dfs(matrix, r - 1, c, dp, &matrix[r][c]));
res = max(res, dfs(matrix, r + 1, c, dp, &matrix[r][c]));
res = max(res, dfs(matrix, r, c + 1, dp, &matrix[r][c]));
res = max(res, dfs(matrix, r, c - 1, dp, &matrix[r][c]));
return dp[r][c] += res;
}
};``````

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