Sunday, August 7, 2016

Given an integer matrix, find the length of the longest increasing path

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
nums = [
Return 4
The longest increasing path is [1, 2, 6, 9].
Strategy: Dynamic Programming
This is a very classic DFS + memorialization problem. If we only use the DFS solution, it will end with many repeated calculations. Therefore, for each element in the matrix[i][j], we use a DP array dp[i][j] to denote the length of the maximum increasing path from this point. So along with the DFS, for a point in the matrix, if we've already found the longest increasing path, we don't have to repeatedly compute it again; we just need to return the length, which is dp[i][j].

One trick here is dp[i][j] stores the length of the longest increasing path. That is because the DFS from a point matrix[i][j] can guarantee the longest path from this point. Since we store this value in the dp[i][j], that can guarantee that dp[i][j] is the longest path from the point matrix[i][j].

No comments:

Post a Comment