Motzkin number | Return the nth Motzkin Number . ; Base case ; Finding i - th Motzkin number . ; Driver code
def motzkin ( n ) : NEW_LINE INDENT dp = [ None ] * ( n + 1 ) NEW_LINE dp [ 0 ] = dp [ 1 ] = 1 ; NEW_LINE i = 2 NEW_LINE while i <= n : NEW_LINE INDENT dp [ i ] = ( ( 2 * i + 1 ) * dp [ i - 1 ] + ( 3 * i - 3 ) * dp [ i - 2 ] ) / ( i + 2 ) ; NEW_LINE i = i + 1 NEW_LINE DEDENT return dp [ n ] ; NEW_LINE DEDENT n = 8 NEW_LINE print ( motzkin ( n ) ) NEW_LINE