Precomputing the countDP prefix sum of the matrix
countDP [ 0 ] [ 0 ] = matrix [ 0 ] [ 0 ] NEW_LINE for i in range ( 1 , R ) : NEW_LINE INDENT countDP [ i ] [ 0 ] = ( countDP [ i - 1 ] [ 0 ] + matrix [ i ] [ 0 ] ) NEW_LINE DEDENT for j in range ( 1 , C ) : NEW_LINE INDENT countDP [ 0 ] [ j ] = ( countDP [ 0 ] [ j - 1 ] + matrix [ 0 ] [ j ] ) NEW_LINE DEDENT for i in range ( 1 , R ) : NEW_LINE INDENT for j in range ( 1 , C ) : NEW_LINE INDENT countDP [ i ] [ j ] = ( matrix [ i ] [ j ] + countDP [ i - 1 ] [ j ] + countDP [ i ] [ j - 1 ] - countDP [ i - 1 ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT