Count of strictly increasing N | Java program for the above approach ; Declaration of dp table ; Function to find the count of all N digit numbers such that all the digit is less than its adjacent digits ; Base Case : If i = n , then return 1 as valid number has been formed ; If the state has already been computed , then return it ; Stores the total count of ways for the current recursive call ; If i = 0 , any digit from [ 1 - 9 ] can be placed and also if N = 1 , then 0 can also be placed ; If i = 1 , any digit from [ 0 - 9 ] can be placed such that digit is not equal to previous digit ; If the current digit is not same as the prev ; Place the current digit such that it is less than the previous digit ; Place current digit such that it is more than the previous digit ; Return the resultant total count ; Function to find all N - digit numbers satisfying the given criteria ; Initialize an array dp [ ] with all elements as - 1 ; Function call to count all possible ways ; Driver Code
import java . util . * ; public class MyClass { static int [ ] [ ] [ ] dp = new int [ 100 ] [ 10 ] [ 2 ] ; static int solve ( int i , int n , int prev , int sign ) { if ( i == n ) { return 1 ; } int val = dp [ i ] [ prev ] [ sign ] ; if ( val != - 1 ) return val ; val = 0 ; if ( i == 0 ) { for ( int digit = ( n == 1 ? 0 : 1 ) ; digit <= 9 ; ++ digit ) { val += solve ( i + 1 , n , digit , sign ) ; } } else if ( i == 1 ) { for ( int digit = 0 ; digit <= 9 ; ++ digit ) { if ( digit != prev ) { val += solve ( i + 1 , n , digit , ( ( digit > prev ) ? 1 : 0 ) ) ; } } } else { if ( sign == 1 ) { for ( int digit = prev - 1 ; digit >= 0 ; -- digit ) { val += solve ( i + 1 , n , digit , 0 ) ; } } else { for ( int digit = prev + 1 ; digit <= 9 ; ++ digit ) { val += solve ( i + 1 , n , digit , 1 ) ; } } } return val ; } static void countNdigitNumber ( int N ) { for ( int [ ] [ ] row : dp ) { for ( int [ ] rowColumn : row ) { Arrays . fill ( rowColumn , - 1 ) ; } } System . out . println ( solve ( 0 , N , 0 , 0 ) ) ; } public static void main ( String args [ ] ) { int N = 3 ; countNdigitNumber ( N ) ; } }