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 = [ [9,9,4], [6,6,8], [2,1,1] ]

Return

The longest increasing path is

`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].

http://www.geeksforgeeks.org/find-the-longest-path-in-a-matrix-with-given-constraints/

http://buttercola.blogspot.in/2016/06/leetcode-329-longest-increasing-path-in.html

http://adijo.github.io/2016/01/20/leetcode-longest-increasing-path-matrix/

## No comments:

## Post a Comment