Count of N | Function to return count of N - digit numbers with absolute difference of adjacent digits not exceeding K ; For 1 - digit numbers , the count is 10 irrespective of K ; dp [ i ] [ j ] stores the number of such i - digit numbers ending in j ; Initialize count for 1 - digit numbers ; Compute values for count of digits greater than 1 ; Find the range of allowed numbers if last digit is j ; Perform Range update ; Prefix sum to find actual values of i - digit numbers ending in j ; Stores the final answer ; Driver Code
function getCount ( n , k ) { if ( n == 1 ) return 10 ; var dp = new Array ( n + 1 ) ; for ( var i = 0 ; i < dp . length ; i ++ ) dp [ i ] = Array ( 11 ) . fill ( 0 ) ; for ( i = 1 ; i <= 9 ; i ++ ) dp [ 1 ] [ i ] = 1 ; for ( i = 2 ; i <= n ; i ++ ) { for ( j = 0 ; j <= 9 ; j ++ ) { var l = Math . max ( 0 , j - k ) ; var r = Math . min ( 9 , j + k ) ; dp [ i ] [ l ] += dp [ i - 1 ] [ j ] ; dp [ i ] [ r + 1 ] -= dp [ i - 1 ] [ j ] ; } for ( j = 1 ; j <= 9 ; j ++ ) dp [ i ] [ j ] += dp [ i ] [ j - 1 ] ; } var count = 0 ; for ( i = 0 ; i <= 9 ; i ++ ) count += dp [ n ] [ i ] ; return count ; } var n = 2 , k = 1 ; document . write ( getCount ( n , k ) ) ;