This content originally appeared on DEV Community and was authored by Wing-Kam WONG
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;
}
This content originally appeared on DEV Community and was authored by Wing-Kam WONG
Wing-Kam WONG | Sciencx (2021-10-02T02:43:55+00:00) BinarySearch – Longest Increasing Path. Retrieved from https://www.scien.cx/2021/10/02/binarysearch-longest-increasing-path/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.