Number of n digit stepping numbers | Space optimized solution | function that calculates the answer ; dp [ j ] stores count of i digit stepping numbers ending with digit j . ; To store resu1lt of length i - 1 before updating dp [ j ] for length i . ; 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 ] * 10 NEW_LINE prev = [ 0 ] * 10 NEW_LINE if ( n == 1 ) : NEW_LINE INDENT return 10 NEW_LINE DEDENT for j in range ( 0 , 10 ) : NEW_LINE INDENT dp [ j ] = 1 NEW_LINE DEDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT for j in range ( 0 , 10 ) : NEW_LINE INDENT prev [ j ] = dp [ j ] NEW_LINE DEDENT for j in range ( 0 , 10 ) : NEW_LINE INDENT if ( j == 0 ) : NEW_LINE INDENT dp [ j ] = prev [ j + 1 ] NEW_LINE DEDENT elif ( j == 9 ) : NEW_LINE INDENT dp [ j ] = prev [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ j ] = prev [ j - 1 ] + prev [ j + 1 ] NEW_LINE DEDENT DEDENT DEDENT sum = 0 NEW_LINE for j in range ( 1 , 10 ) : NEW_LINE INDENT sum = sum + dp [ j ] NEW_LINE DEDENT return sum NEW_LINE DEDENT n = 2 NEW_LINE print ( answer ( n ) ) NEW_LINE