Count of non | C # program for the above approach ; Define the dp table globally ; Recursive function to calculate total number of valid non - decreasing strings ; If already calculated state ; Base Case ; Stores the total count of strings formed ; Fill the value in dp matrix ; Function to find the total number of non - decreasing string formed by replacing the ' ? ' ; Initialize all value of dp table with - 1 ; Left and Right limits ; Iterate through all the characters of the string S ; Change R to the current character ; Call the recursive function ; Change L to R and R to 9 ; Reinitialize the length of ? to 0 ; Increment the length of the segment ; Update the ans ; Return the total count ; Driver Code
using System ; using System . Collections . Generic ; class GFG { static int MAXN = 100005 ; static int [ , ] dp = new int [ MAXN , 10 ] ; static int solve ( int len , int gap ) { if ( dp [ len , gap ] != - 1 ) { return dp [ len , gap ] ; } if ( len == 0 gap == 0 ) { return 1 ; } if ( gap < 0 ) { return 0 ; } int ans = 0 ; for ( int i = 0 ; i <= gap ; i ++ ) { ans += solve ( len - 1 , gap - i ) ; } return dp [ len , gap ] = ans ; } static int countValidStrings ( string S ) { for ( int i = 0 ; i < MAXN ; i ++ ) { for ( int j = 0 ; j < 10 ; j ++ ) { dp [ i , j ] = - 1 ; } } int N = S . Length ; int L = 1 , R = 9 ; int cnt = 0 ; int ans = 1 ; for ( int i = 0 ; i < N ; i ++ ) { if ( S [ i ] != ' ? ' ) { R = ( int ) S [ i ] - 48 ; ans *= solve ( cnt , R - L ) ; L = R ; R = 9 ; cnt = 0 ; } else { cnt ++ ; } } ans *= solve ( cnt , R - L ) ; return ans ; } public static void Main ( ) { string S = "1 ? ? ?2" ; Console . Write ( countValidStrings ( S ) ) ; } }