BinarySearch - Longest Increasing Path

https://binarysearch.com/problems/Longest-Increasing-Path

Problem

Given a two-dimensional integer matrix, find the length of the longest strictly increasing path. You can move up, down, left, or right.

Constraints

n, m ≤ 500 where n and m are the number of rows and columns in matrix

Solution

DFS Approach.

dp[i][j] means the length of longest increasing path starting from (i,j). Traverse four directions iff the next cell is in the bound and the value is greater than the current one. Calculate it recursively and store it back to dp[i][j]. If dp[i][j] has been calculated, return the cached result directly.

int m, n;
vector<vector<int>> dp;

int dfs(vector<vector<int>>& matrix, int i, int j) {
    if (dp[i][j]) return dp[i][j];
    int v = 1;
    if (i + 1 < m && matrix[i + 1][j] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i + 1, j));
    if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i - 1, j));
    if (j + 1 < n && matrix[i][j + 1] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i, j + 1));
    if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i, j - 1));
    dp[i][j] = v;
    return dp[i][j];
}

int solve(vector<vector<int>>& matrix) {
    m = matrix.size(), n = matrix[0].size();
    dp = vector<vector<int>>(m, vector<int>(n, 0));
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, dfs(matrix, i, j));
        }
    }
    return ans;
}