Longest Increasing Path in Matrix | Python3 program to find longest increasing path in a matrix . ; Return the length of LIP in 2D matrix ; If value not calculated yet . ; If reach bottom left cell , return 1. ; If reach the corner of the matrix . ; If value greater than below cell . ; If value greater than left cell . ; Wrapper function ; Driver Code
MAX = 20 NEW_LINE def LIP ( dp , mat , n , m , x , y ) : NEW_LINE INDENT if ( dp [ x ] [ y ] < 0 ) : NEW_LINE INDENT result = 0 NEW_LINE if ( x == n - 1 and y == m - 1 ) : NEW_LINE INDENT dp [ x ] [ y ] = 1 NEW_LINE return dp [ x ] [ y ] NEW_LINE DEDENT if ( x == n - 1 or y == m - 1 ) : NEW_LINE INDENT result = 1 NEW_LINE DEDENT if ( x + 1 < n and mat [ x ] [ y ] < mat [ x + 1 ] [ y ] ) : NEW_LINE INDENT result = 1 + LIP ( dp , mat , n , m , x + 1 , y ) NEW_LINE DEDENT if ( y + 1 < m and mat [ x ] [ y ] < mat [ x ] [ y + 1 ] ) : NEW_LINE INDENT result = max ( result , 1 + LIP ( dp , mat , n , m , x , y + 1 ) ) NEW_LINE DEDENT dp [ x ] [ y ] = result NEW_LINE DEDENT return dp [ x ] [ y ] NEW_LINE DEDENT def wrapper ( mat , n , m ) : NEW_LINE INDENT dp = [ [ - 1 for i in range ( MAX ) ] for i in range ( MAX ) ] NEW_LINE return LIP ( dp , mat , n , m , 0 , 0 ) NEW_LINE DEDENT mat = [ [ 1 , 2 , 3 , 4 ] , [ 2 , 2 , 3 , 4 ] , [ 3 , 2 , 3 , 4 ] , [ 4 , 5 , 6 , 7 ] ] NEW_LINE n = 4 NEW_LINE m = 4 NEW_LINE print ( wrapper ( mat , n , m ) ) NEW_LINE