Count of N | C # Program to implement the above approach ; Function to return the count of N - digit numbers with absolute difference of adjacent digits not exceeding K ; For 1 - digit numbers , the count is 10 ; dp [ i ] [ j ] stores the count of i - digit numbers ending with j ; Initialize count for 1 - digit numbers ; Compute values for count of digits greater than 1 ; Find the range of allowed numbers with last digit j ; Perform Range update ; Prefix sum to count i - digit numbers ending in j ; Stores the final answer ; Driver Code
using System ; class GFG { static long getCount ( int n , int k ) { if ( n == 1 ) return 10 ; long [ , ] dp = new long [ n + 1 , 11 ] ; for ( int i = 1 ; i <= 9 ; i ++ ) dp [ 1 , i ] = 1 ; for ( int i = 2 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= 9 ; j ++ ) { int l = Math . Max ( 0 , j - k ) ; int r = Math . Min ( 9 , j + k ) ; dp [ i , l ] += dp [ i - 1 , j ] ; dp [ i , r + 1 ] -= dp [ i - 1 , j ] ; } for ( int j = 1 ; j <= 9 ; j ++ ) dp [ i , j ] += dp [ i , j - 1 ] ; } long count = 0 ; for ( int i = 0 ; i <= 9 ; i ++ ) count += dp [ n , i ] ; return count ; } public static void Main ( ) { int n = 2 , k = 1 ; Console . WriteLine ( getCount ( n , k ) ) ; } }