C# 232 ms I worked on this for 3 hours, how can it be improved, it now uses dp


  • 0
    K
    public class Solution {
        public int LongestIncreasingPath(int[,] matrix) {
            int h = matrix.GetLength(0);
            int v = matrix.GetLength(1);
            if(h == 0) return 0;
            int biggest = 0;
            int[,] memo = new int[h,v];    
            int temp = 0;
            for(int i = 0; i < h; i++)
            {
                for(int j = 0; j < v; j++)
                    memo[i, j] = -1;
            }
            
            for(int i = 0; i < h; i++)
            {
                for(int j = 0; j < v; j++)
                {
                    if(memo[i, j] != -1)
                    {
                        biggest = memo[i, j] > biggest ? memo[i, j] : biggest;
                        continue;
                    }
                    temp = Steps(matrix, h, v, i, j, 0, ref memo);
                    biggest = temp > biggest ? temp : biggest;
                }
            }
            return biggest + 1;
        }
        
        public int Steps(int[,] matrix, int h1, int v1, int x, int y, int count, ref int[,] memo1)
        {
            bool canGo = false;
            int a = 0;
            int b = 0;
            int c = 0;
            int d = 0;
            if(x + 1 < h1 && matrix[x+1,y] > matrix[x,y])
            {
                if(memo1[x+1, y] != -1) a = memo1[x+1,y] + 1;
                else a = Steps(matrix, h1, v1, x+1, y, ++count, ref memo1) + 1; 
                canGo = true;
            }
            if(y + 1 < v1 && matrix[x, y+1] > matrix[x,y])
            {
                if(memo1[x, y+1] != -1) b = memo1[x,y+1] + 1;
                else b = Steps(matrix, h1, v1, x, y+1, ++count, ref memo1) + 1;
                canGo = true;
            }
            if(x - 1 >= 0 && matrix[x-1,y] > matrix[x,y])
            {
                if(memo1[x-1, y] != -1) c = memo1[x-1,y] + 1;
                else c = Steps(matrix, h1, v1, x-1, y, ++count, ref memo1) + 1;
                canGo = true;
            }
            if(y - 1 >= 0 && matrix[x, y-1] > matrix[x,y])
            {
                if(memo1[x, y-1] != -1) d = memo1[x,y-1] + 1;
                else d = Steps(matrix, h1, v1, x, y-1, ++count, ref memo1) + 1;
                canGo = true;
            }
            
            if(canGo == false)
            {
                memo1[x, y] = 0;
                return 0;
            }
            else
            {
                int abBigger = a > b ? a : b;
                int cdBigger = c > d ? c : d;
                int result = abBigger > cdBigger ? abBigger : cdBigger;
                memo1[x, y] = result;
                return result;
            }
        }
    }

  • 0
    Z

    Do not do recursion. It would be passed


  • 0
    K

    Makes sense.


  • 0
    K

    https://leetcode.com/discuss/81342/java-solution-o-mn-backtracking-dfs-dp-accepted I found this post to be very similar to mine,still haven't figured out how to do this without recursion though.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.