# 329 Longest Increasing Path

這一題有一點點困難，因為直覺上的做法會用到遞迴的觀念，而且只是用遞迴的話無法通過測資（有些case會跑太久，超出時間），所以還必須把計算過的結果存起來(memoization)。

關於Memoization跟Dynamic Programming的差別，可以看一下這個討論串。

直觀上的做法其實很簡單，就是go through整個matrix，然後把每個element的longest increasing path的長度拿來比較，回傳最長的那一個就好。至於要怎麼找到每一個element的longest increasing path長度，那就用findLongestIncreasingPath()這個函式來處理。

public class Solution {
    int[][] lengthMatrix ;
    public int longestIncreasingPath(int[][] matrix) {
        //Concept:
        //visit each element
        //  find the longest increasing path of it(findLongestIncreasingPath())
        //return the longest increasing path of all elements

        //findLongestIncreasingPath(matrix, element):
        //  if all neighbors are smaller than element, return 1,
        //  if find any neighbor larger than element, call find LongestIncreasingPath again
        //output: length of longest increasing path of this element
        /*
        ９９９
        ６７８
        １２３
        given input：matrix, element １
        output：５

        if all neighbor <＝element, return １

        length_list＝get the length of longest increasing path of each neighbor that are larger than １（neighbor要大於１
        ）

        return max（length_list）+1
        */

        //Pseudo Code
        /*int longestIncreasingPath(int[][] matrix)
        if(matrix is empty) return 0;
        if(matrix is  1x1) return 1;

        int maxLenght=0, lenght=0;    
        for each element in matrix:
            length = findLongestIncreasingPath(matrix, element);
            if(length > maxLength) maxLength = length;

        return maxLength;

        int findLongestIncreasingPath(matrix, element):
            if(all neighbor <= element) return 1;

            int length, maxLength;
            for all neighbors that are larger than 1
            length＝get the length of longest increasing path of each neighbor that are larger than 1
            if(length > maxLength) maxLength = length;

            return maxLength+1
        */
        int m = matrix.length;
        if(m == 0)  return 0;
        int n = matrix[0].length;
        if(m == 1 && n == 1) return 1;

        //int[][] 
        lengthMatrix = new int[m][n];
        int maxLength=0, length=0;  
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(lengthMatrix[i][j]==0)
                    length = findLongestIncreasingPath(matrix, i, j, m, n);
                else
                    length = lengthMatrix[i][j];
                if(length > maxLength) maxLength = length;
            }
        }
        return maxLength;

    }

    int findLongestIncreasingPath(int[][] matrix, int i, int j, int m, int n){
        /*nums = [
          [9,9,4],
          [6,6,8],
          [2,1,1]
          i=2, j=1
        ]*/

        int length=0, maxLength=0;
        for(int p = -1; p<=1; p++){
            for(int q = -1; q<=1; q++){
                if(p==q || p+q==0)  continue;
                if(i+p>=0 && i+p<m && j+q>=0 && j+q<n && matrix[i+p][j+q]>matrix[i][j]){
                    if(lengthMatrix[i+p][j+q]==0){
                        length = findLongestIncreasingPath(matrix, i+p, j+q, m, n);
                        lengthMatrix[i+p][j+q]=length;
                    }
                    else
                        length = lengthMatrix[i+p][j+q];
                }
                if(length > maxLength) maxLength = length;   
            }
        }
        return maxLength + 1;
    }
}