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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAXN  100005 NEW_LINE int dp [ MAXN ] [ 10 ] ; 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 ; } int countValidStrings ( string S ) { memset ( dp , -1 , sizeof ( dp ) ) ; 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 = S [ i ] - '0' ; ans *= solve ( cnt , R - L ) ; L = R ; R = 9 ; cnt = 0 ; } else { cnt ++ ; } } ans *= solve ( cnt , R - L ) ; return ans ; } int main ( ) { string S = "1 ? ? ?2" ; cout << countValidStrings ( S ) ; return 0 ; }