## DEV Community is a community of 787,776 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Wing-Kam WONG

Posted on

# 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;
}
``````