Count of non decreasing Arrays with ith element in range [ A [ i ] , B [ i ] ] | C # program for the above approach ; Function to count the total number of possible valid arrays ; Make a 2D DP table ; Make a 2D prefix sum table ; Initialize all values to 0 ; Base Case ; Initialize the prefix values ; Iterate over the range and update the dp table accordingly ; Add the dp values to the prefix sum ; Update the prefix sum table ; Find the result count of arrays formed ; Return the total count of arrays ; Driver Code
using System ; class GFG { static int totalValidArrays ( int [ ] a , int [ ] b , int N ) { int [ , ] dp = new int [ N + 1 , b [ N - 1 ] + 1 ] ; int [ , ] pref = new int [ N + 1 , b [ N - 1 ] + 1 ] ; for ( int i = 0 ; i < N + 1 ; i ++ ) for ( int j = 0 ; j < b [ N - 1 ] + 1 ; j ++ ) dp [ i , j ] = 0 ; for ( int i = 0 ; i < N + 1 ; i ++ ) for ( int j = 0 ; j < b [ N - 1 ] + 1 ; j ++ ) pref [ i , j ] = 0 ; dp [ 0 , 0 ] = 1 ; for ( int i = 0 ; i <= b [ N - 1 ] ; i ++ ) { pref [ 0 , i ] = 1 ; } for ( int i = 1 ; i <= N ; i ++ ) { for ( int j = a [ i - 1 ] ; j <= b [ i - 1 ] ; j ++ ) { dp [ i , j ] += pref [ i - 1 , j ] ; pref [ i , j ] += dp [ i , j ] ; } for ( int j = 0 ; j <= b [ N - 1 ] ; j ++ ) { if ( j > 0 ) { pref [ i , j ] += pref [ i , j - 1 ] ; } } } int ans = 0 ; for ( int i = a [ N - 1 ] ; i <= b [ N - 1 ] ; i ++ ) { ans += dp [ N , i ] ; } return ans ; } public static void Main ( ) { int [ ] A = { 1 , 1 } ; int [ ] B = { 2 , 3 } ; int N = A . Length ; Console . WriteLine ( totalValidArrays ( A , B , N ) ) ; } }