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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int totalValidArrays ( int a [ ] , int b [ ] , int N ) { int dp [ N + 1 ] [ b [ N - 1 ] + 1 ] ; int pref [ N + 1 ] [ b [ N - 1 ] + 1 ] ; memset ( dp , 0 , sizeof ( dp ) ) , memset ( pref , 0 , sizeof ( pref ) ) ; 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 ; } int main ( ) { int A [ ] = { 1 , 1 } ; int B [ ] = { 2 , 3 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << totalValidArrays ( A , B , N ) ; return 0 ; }