Number of n digit stepping numbers | function that calculates the answer ; dp [ i ] [ j ] stores count of i digit stepping numbers ending with digit j . ; if n is 1 then answer will be 10. ; Initialize values for count of digits equal to 1. ; Compute values for count of digits more than 1. ; If ending digit is 0 ; If ending digit is 9 ; For other digits . ; stores the final answer ; Driver Code
def answer ( n ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( 10 ) ] for y in range ( n + 1 ) ] ; NEW_LINE if ( n == 1 ) : NEW_LINE INDENT return 10 ; NEW_LINE DEDENT for j in range ( 10 ) : NEW_LINE INDENT dp [ 1 ] [ j ] = 1 ; NEW_LINE DEDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT for j in range ( 10 ) : NEW_LINE INDENT if ( j == 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j + 1 ] ; NEW_LINE DEDENT elif ( j == 9 ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j - 1 ] ; NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = ( dp [ i - 1 ] [ j - 1 ] + dp [ i - 1 ] [ j + 1 ] ) ; NEW_LINE DEDENT DEDENT DEDENT sum = 0 ; NEW_LINE for j in range ( 1 , 10 ) : NEW_LINE INDENT sum = sum + dp [ n ] [ j ] ; NEW_LINE DEDENT return sum ; NEW_LINE DEDENT n = 2 ; NEW_LINE print ( answer ( n ) ) ; NEW_LINE