[LeetCode]Longest Increasing Path in a Matrix

Matrix的问题有的时候可以转化成图的问题来求解。对于这道题也是一样，我们可以转化成有向图，每一个cell就是一个vertex。而每一个vertex有四个可能的邻节点，如果相邻节点a的值大于当前节点值，那么可以视作从当前节点有一条有向边去向节点a。根据这个原则，我们可以把图给建起来。值得注意的是，这个图没有环，因为假设存在环的话，对于环上的每个节点我们有n1 < n2 < n3 <...< nk < n1，这是不可能出现的。那么这道题就可以转外成求DAG里面的最长路径问题，dfs当然可以做，但是显然会超时。Topological sorting可以解决这个问题，DAG里的最长路径就是topological sorting之后的最长路径，把每一层没有indegree或者outdegree的节点去掉，最后的层数就是我们要的最长路径。代码如下：

时间复杂度O(V + E) = O(m * n)，空间复杂度O(m * n)。
如果在dfs的时候做memorization的优化，也可以达到我们想要的结果。时间复杂度也是O(V + E) = O(m * n)，因为对于每一个节点和每一条边都只会计算一次了。空间复杂度O(m * n)。代码如下：