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
< ? php function answer ( $ n ) { $ dp = array_fill ( 0 , 10 , 0 ) ; $ prev = array_fill ( 0 , 10 , 0 ) ; ; if ( $ n == 1 ) return 10 ; for ( $ j = 0 ; $ j <= 9 ; $ j ++ ) $ dp [ $ j ] = 1 ; for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) { for ( $ j = 0 ; $ j <= 9 ; $ j ++ ) { $ prev [ $ j ] = $ dp [ $ j ] ; } for ( $ 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 ] ; } } $ sum = 0 ; for ( $ j = 1 ; $ j <= 9 ; $ j ++ ) $ sum += $ dp [ $ j ] ; return $ sum ; } $ n = 2 ; echo answer ( $ n ) ; ? >