Leetcode 329 - Longest Increasing Path in a matrix - DFS, memorization, first practice

Leetcode329LongestIncreasingPathInaMatrix.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _329MatrixMaximPathLength
{
    class Program
    {
        /*
         * Leetcode 329: 
         * 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).
         *  
         * nums = [
              [9,9,4],
              [6,6,8],
              [2,1,1]
            ]
         * 
         * return 4  - 
         * 9
         * 6
         * 2 1
         * the path from 1 -> 2 -> 6->9
         * 
         */
        static void Main(string[] args)
        {
            int[][] matrix = new int[3][]{
                new int[3]{9, 9, 4}, 
                new int[3]{6, 6, 8},
                new int[3]{2, 1, 1}
            };

            int result = longestIncreasingPath(matrix); 
            // verify result: 4 

        }

        /*
         * Java code from blog:
         * http://blog.csdn.net/sbitswc/article/details/50707203
         */

        public static int longestIncreasingPath(int[][] matrix) {  
            if(matrix.Length<=0 || matrix[0].Length <=0) 
                return 0;  

            int max=0, 
                rows = matrix.Length, 
                cols = matrix[0].Length;  

            int [][] cache = new int[rows][];
            for (int i = 0; i < rows; i++)
                cache[i] = new int[cols];

            int testValue = maxLen(matrix, Int32.MinValue, 2, 1, cache); 

            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < cols; j++)
                {
                    max = Math.Max(max, maxLen(matrix, Int32.MinValue, i, j, cache));
                }
            }  

            return max;  
        }

        /*
         * write down something to help:
         * 
         * Using DFS - depth first search          
         * memorization - use cache array to store the result 
         * 
         * min - previous node's value - so, it is minimum value to compare
         * 
         * checkpoints:
         * 1. Run time problem - array out of index
         * 2. Value - wrong value
         * 3. logic checking 
         * 4. memorization - remove duplication calculation 
         * 
         */
        public static int maxLen(int[][] matrix, int nodeValue, int startX, int startY, int[][] cache)
        {
            // base cases: 
            if (startX < 0 || 
                startY < 0 || 
                startX >= matrix.Length || 
                startY >= matrix[0].Length)
            {
                return 0;
            }

            // increasing path - next node should be bigger value 
            if (matrix[startX][startY] <= nodeValue)
            {
                return 0;
            }

            // memorization 
            if (cache[startX][startY] != 0)
            {
                return cache[startX][startY];
            }

            nodeValue = matrix[startX][startY];

            // Four neighbors - left, right, up, down 
            int[][] neighbors = new int[4][]{
                new int[2]{-1, 0}, 
                new int[2]{0, -1}, 
                new int[2]{0, 1}, 
                new int[2]{1, 0}
            };

            // get maximum value from 4 neighbors 
            int maxValue = 0; 
            for (int i = 0; i < neighbors.Length; i++)
            {
                int nextX = startX + neighbors[i][0];
                int nextY = startY + neighbors[i][1];

                // pathLength value increments by one 
                int pathLength  = maxLen(matrix, nodeValue, nextX, nextY, cache) + 1;
                maxValue = pathLength > maxValue ? pathLength : maxValue;                     
            }            
            
            cache[startX][startY] = maxValue;

            return cache[startX][startY];
        }  
    }
}