Count number of ways to reach a given score in a Matrix | Python3 implementation of the approach ; To store the states of dp ; To check whether a particular state of dp has been solved ; Function to find the ways using memoization ; Base cases ; If required score becomes negative ; If current state has been reached before ; Set current state to visited ; Driver code
n = 3 NEW_LINE MAX = 60 NEW_LINE dp = [ [ [ 0 for i in range ( 30 ) ] for i in range ( 30 ) ] for i in range ( MAX + 1 ) ] NEW_LINE v = [ [ [ 0 for i in range ( 30 ) ] for i in range ( 30 ) ] for i in range ( MAX + 1 ) ] NEW_LINE def findCount ( mat , i , j , m ) : NEW_LINE INDENT if ( i == 0 and j == 0 ) : NEW_LINE INDENT if ( m == mat [ 0 ] [ 0 ] ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT else : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT if ( m < 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( i < 0 or j < 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( v [ i ] [ j ] [ m ] > 0 ) : NEW_LINE INDENT return dp [ i ] [ j ] [ m ] NEW_LINE DEDENT v [ i ] [ j ] [ m ] = True NEW_LINE dp [ i ] [ j ] [ m ] = ( findCount ( mat , i - 1 , j , m - mat [ i ] [ j ] ) + findCount ( mat , i , j - 1 , m - mat [ i ] [ j ] ) ) NEW_LINE return dp [ i ] [ j ] [ m ] NEW_LINE DEDENT mat = [ [ 1 , 1 , 1 ] , [ 1 , 1 , 1 ] , [ 1 , 1 , 1 ] ] NEW_LINE m = 5 NEW_LINE print ( findCount ( mat , n - 1 , n - 1 , m ) ) NEW_LINE