Count of non decreasing Arrays with ith element in range [ A [ i ] , B [ i ] ] | Function to count the total number of possible valid arrays ; Make a 2D DP table ; Make a 2D prefix sum table ;  ; Base Case ; Initialize the prefix values ; Iterate over the range and update the dp table accordingly ; Add the dp values to the prefix sum ; Update the prefix sum table ; Find the result count of arrays formed ; Return the total count of arrays ; Driver Code
def totalValidArrays ( a , b , N ) : NEW_LINE INDENT dp = [ [ 0 for _ in range ( b [ N - 1 ] + 1 ) ] for _ in range ( N + 1 ) ] NEW_LINE pref = [ [ 0 for _ in range ( b [ N - 1 ] + 1 ) ] for _ in range ( N + 1 ) ] NEW_LINE DEDENT / * Initialize all values to 0 * / NEW_LINE INDENT dp [ 0 ] [ 0 ] = 1 NEW_LINE for i in range ( 0 , b [ N - 1 ] + 1 ) : NEW_LINE INDENT pref [ 0 ] [ i ] = 1 NEW_LINE DEDENT for i in range ( 1 , N + 1 ) : NEW_LINE INDENT for j in range ( a [ i - 1 ] , b [ i - 1 ] + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] += pref [ i - 1 ] [ j ] NEW_LINE pref [ i ] [ j ] += dp [ i ] [ j ] NEW_LINE DEDENT for j in range ( 0 , b [ N - 1 ] + 1 ) : NEW_LINE INDENT if ( j > 0 ) : NEW_LINE INDENT pref [ i ] [ j ] += pref [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT DEDENT ans = 0 NEW_LINE for i in range ( a [ N - 1 ] , b [ N - 1 ] + 1 ) : NEW_LINE INDENT ans += dp [ N ] [ i ] NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 1 , 1 ] NEW_LINE B = [ 2 , 3 ] NEW_LINE N = len ( A ) NEW_LINE print ( totalValidArrays ( A , B , N ) ) NEW_LINE DEDENT