text: Number of n digit stepping numbers | Space optimized solution | C # program to calculate the number of n digit stepping numbers . ; 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 code
code: using System ; class GFG { static long answer ( int n ) { int [ ] dp = new int [ 10 ] ; int [ ] prev = new int [ 10 ] ; if ( n == 1 ) return 10 ; for ( int j = 0 ; j <= 9 ; j ++ ) dp [ j ] = 1 ; for ( int i = 2 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= 9 ; j ++ ) { prev [ j ] = dp [ j ] ; } for ( int 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 ] ; } } long sum = 0 ; for ( int j = 1 ; j <= 9 ; j ++ ) sum += dp [ j ] ; return sum ; } static void Main ( ) { int n = 2 ; Console . WriteLine ( answer ( n ) ) ; } }