DP | O(n*max(nums[i])) | Summation |
Let say at index i, current number(nums[i]) is y and at index i - 1 the nums[i - 1] is x\n\nNote that arr1[i - 1] <= x\nLets say arr1[i - 1] = k\n=> k <= x \u20
Let say at index i, current number(nums[i]) is `y` and at index i - 1 the nums[i - 1] is `x`\n\nNote that `arr1[i - 1] <= x`\nLets say `arr1[i - 1] = k`\n=> `k <= x` \u2026 **cond 1**\nNow, `arr2[i - 1] = x - k`\nLets say we have solution till `i-1` for each k < x.\n\nNow for current element\n`arr1[i] <= y`\nLets say `arr1[i] = j`\n=> `arr2[i] = y - j`\n\nSince,\n`arr1[i - 1] <= arr1[i]`\n=> `k <=  j` \u2026 **cond 2**\nAlso,\n`arr2[i - 1] >= arr2[i]`\n=> `x - k >= y - j`\n=> `k <= x - y + j` \u2026 **cond 3**\n\nAlso note that since non-negative integers are to be chosen, both\n`j >= 0`\n`k >= 0` \u2026 **cond 4**\n\nNow for any `j` all `k` from previous `i-1`th solution will contribute to current solution at `arr1[i]=j`\nwhich satisfies each of cond1, cond2, cond3, cond4\n\n=> `k >= 0` and `k <= min(x, j, x - y + j)`\n\ni.e `Sol[arr1[i] == j] = `**Sum(**`Sol[arr1[i - 1] == k]`**)**` for k = 0, 1, \u2026 min(x, j, x-y+j)` \u2026 equation 1\n\n=> If we store summation of solution that will be more benificial.\nLets say **SolSum**`[i, m] = `**Sum(**`Sol[arr1[i] == c]`**)**` for c  = 0, 1, \u2026m`\nthen,  **SolSum**`[i,  j] = `**SolSum**`[i,  j  - 1] + Sol[arr1[i] == j]`\n\n=> **SolSum**`[i,  j] = `**SolSum**`[i,  j  - 1] + `**SolSum**`[i - 1,  min(x, j, x-y+j)]` (from equation 1)\n\nThis will hence calculate the desired solution in **O(n\\*max(nums[i]))**.\n\nFollowing solution assumed max(nums[i]) == 1001. It can be also pre-searched in nums instead.\n```\nclass Solution {\npublic:\n    int countOfPairs(vector<int>& nums) {\n        int m = 1e9 + 7;\n        vector<vector<int> >table (2, vector<int>(1001, 0));\n        for(int i = 0; i <= nums[0]; i++) table[0][i] = i+1;\n        for(int i = nums[0] + 1; i < 1001; i++) table[0][i] = nums[0]+1;\n        int x, y, k;\n        int c = 1;\n        int l;\n        for(int i = 1; i < nums.size(); i++){\n            x = nums[i - 1];\n            y = nums[i];\n            l = 0;\n            for(int j = 0; j <= y; j++){\n                table[c][j] = l;\n                k = min(j, x);\n                k = min(x - y + j, k);\n                if(k >= 0){\n                    table[c][j] = (table[c][j] + table[c^1][k])%m;\n                }\n                l = table[c][j];\n            }\n            for(int j = y + 1; j < 1001; j++) table[c][j] = l;\n            c ^= 1;\n        }\n        c ^= 1;\n        return table[c].back();      \n    }\n};\n```
['Dynamic Programming', 'Prefix Sum']