2 Approach | Easy Explanation | Tabulation | Combinatoricsd
Dynamic Programming \n\n\nclass Solution {\npublic:\n\n    int mod = 1e9 + 7 ;\n\n    int countOfPairs(vector<int>& nums) {\n\n        // initialize n and 2D dp
# Dynamic Programming \n\n```\nclass Solution {\npublic:\n\n    int mod = 1e9 + 7 ;\n\n    int countOfPairs(vector<int>& nums) {\n\n        // initialize n and 2D dp \n        // dp[i][j] -> No of ways of generating array till index i having a[i] = j  \n        // answer will be summation of dp[n-1][j]  where  0 <= j <= 1000 \n        int n = nums.size() ;\n        int dp[n+1][1001], pref[n+1][1001] ;\n        memset(dp,0,sizeof(dp)) ;\n        memset(pref,0,sizeof(pref)) ;\n\n        // for the 0 index for every j <= nums[0] the dp[0][j] will be 1 as there is 1 way\n        for(int j = 0 ; j <= nums[0] ; j++ ){\n            dp[0][j] = 1 ;\n            pref[0][j] = dp[0][j] + ( j ? pref[0][j-1] : 0 ) ;\n        } \n        \n        // now iterating over the index of array for every index, iterating over every possible\n        // value of a that is  0 <= a <= nums[i], calculate b = nums[i] - a.\n        // Now check for every possible value of prev_a. Two condition to be hold \n        // 1) 0 <= prev_a <= nums[i-1] \n        // 2) prev_a <= a\n\n        // Intersection Of Both :  0 <= prev_a <= min( a, nums[i-1] ) ;\n        // Now calculte prev_b = nums[i-1] - prev_a and check for conditon that prev_b >= b \n\n        // as prev_a is increasing so prev_b will be decreasing  if at any moment prev_b < b then break \n        // else add dp[i-1][prev_a] to ways \n\n        // dp[i][prev_a] = ways ;\n\n        // Mathametical computation :\n        // -> prev_b < b \n        // -> nums[i-1] - prev_a < nums[i] - a \n        // -> prev_a >  a - ( nums[i] - nums[i-1] ) \n        // -> 0 <= prev_a <= min(a, nums[i-1], a - ( nums[i] - nums[i-1] ) ) ;\n        // Now we are adding for every prev_a from a to this so compute this earlier \n        \n        \n        for(int i = 1 ; i < n ; i++ ){\n            for(int a = 0 ; a <= nums[i] ; a++ ){\n                int b = nums[i] - a ;\n                int ways = 0 ;\n\n                // for(int prev_a = 0 ; prev_a <= min(a, nums[i-1]) ; prev_a++ ){\n                //     int prev_b = nums[i-1] - prev_a ;\n                //     if(prev_b < b ) break ;\n                //     ways = (ways + dp[i-1][prev_a] ) % mod ;\n                // }\n\n                int prev_a = min( a, min( nums[i-1], a - ( nums[i] - nums[i-1] ))) ;\n\n                ways =  ( prev_a<0 ? 0 : pref[i-1][prev_a] ); \n                dp[i][a] = ways ; \n                pref[i][a] = ( dp[i][a] + ( a ? pref[i][a-1] : 0 ) ) % mod  ;\n            }\n        }\n\n        int res = 0 ; \n        for(int i = 0 ; i <= 1000 ; i++ ){\n            res = (res + dp[n-1][i] ) % mod ;\n        }\n        return res ;\n    }\n};\n```\n\n# Combinatorics\nThis Combinatorics Explanation is Taken from [Here](https://leetcode.com/problems/find-the-count-of-monotonic-pairs-ii/solutions/5620214/on-solution-using-maths/)\nSpecial Thanks to [404_not_found__](https://leetcode.com/u/404_not_found__/) For Such Explanation \n\n![image.png](https://assets.leetcode.com/users/images/59b568cd-ba69-4aeb-a5f5-f18ee232fc2f_1723369254.2951167.png)\n\nFrom this, we can conclude that whenever an element in the main array increases, we must add the difference to either the increasing array or the decreasing array. However, since we cannot add it to the decreasing array, it must be added to the increasing array.\n\nSimilarly, if the element decreases, the difference must be subtracted from the decreasing array.\n\nSince the elements in both arrays must be greater than or equal to 0, the last element in the decreasing array must also be greater than or equal to 0. From this condition, we can determine the minimum value of the first element in the decreasing array. The range for the first element in the decreasing array can therefore be from this minimum value up to (arr[0] - mini).\n\nThis difference, (remain = arr[0] -mini ), can be used at any index to increase the corresponding element in the increasing array and decrease the corresponding element in the decreasing array. Additionally, there\'s an option to leave the arrays unchanged. Consequently, there are ( n+1 ) choices for the "remain" element.\n\nUsing combinatorial mathematics, the number of possible ways to distribute the "remain" element across the arrays can be calculated using the formula ( n + r - 1 C n - 1).\n\n```\nconst int MAX = 5e3;\nconst int MOD = 1e9 + 7;\nvector<long long> factorial(5e3), inv_factorial(5e3);\nclass Solution {\npublic:\n    Solution(){\n        precompute();\n    }\n    long long mod_pow(long long x, long long y, int mod) {\n        long long result = 1;\n        while (y > 0) {\n            if (y % 2 == 1) {\n                result = (result * x) % mod;\n            }\n            x = (x * x) % mod;\n            y /= 2;\n        }\n        return result;\n    }\n    void precompute() {\n        factorial[0] = factorial[1] = 1;\n        for (int i = 2; i < MAX; ++i) {\n            factorial[i] = (factorial[i - 1] * i) % MOD;\n        }\n        inv_factorial[MAX - 1] = mod_pow(factorial[MAX - 1], MOD - 2, MOD);\n        for (int i = MAX - 2; i >= 0; --i) {\n            inv_factorial[i] = (inv_factorial[i + 1] * (i + 1)) % MOD;\n        }\n    }\n\n    long long nCr(int n, int r) {\n        if (r > n)\n            return 0;\n        return factorial[n] * inv_factorial[r] % MOD * inv_factorial[n - r] %\n               MOD;\n    }\n\n    int countOfPairs(vector<int>& arr) {\n        \n        int mini = 0; // minimum value of first element in decreasing array\n        int n = arr.size();\n        for (int i = 1; i < n; i++) {\n            if (arr[i - 1] > arr[i]) {\n                mini += (arr[i - 1] - arr[i]);\n            }\n        }\n        int remain = arr[0] - mini;\n        if (remain < 0)\n            return 0;\n        n++; // n+1 choices\n        return nCr(n + remain - 1, n - 1);\n    }\n};\n```
['Math', 'Dynamic Programming', 'Combinatorics', 'C++']