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 result 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 program to test the above function
function answer ( n ) { var dp = Array ( 10 ) ; var prev = Array ( 10 ) ; if ( n == 1 ) return 10 ; for ( var j = 0 ; j <= 9 ; j ++ ) dp [ j ] = 1 ; for ( var i = 2 ; i <= n ; i ++ ) { for ( var j = 0 ; j <= 9 ; j ++ ) { prev [ j ] = dp [ j ] ; } for ( var j = 0 ; j <= 9 ; j ++ ) { if ( j == 0 ) dp [ j ] = prev [ j + 1 ] ; else if ( j == 9 ) dp [ j ] = prev [ j - 1 ] ; else dp [ j ] = prev [ j - 1 ] + prev [ j + 1 ] ; } } var sum = 0 ; for ( var j = 1 ; j <= 9 ; j ++ ) sum += dp [ j ] ; return sum ; } var n = 2 ; document . write ( answer ( n ) ) ;