DP + prefix w/ explanation
The intuition is similar to Find the Count of Monotonic Pairs I, but in this question, the nums[i] range [0, 1000] is too large to use normal iteration, so we u
The intuition is similar to [Find the Count of Monotonic Pairs I](https://leetcode.com/problems/find-the-count-of-monotonic-pairs-i/discuss/5620080/2D-DP1D-DPDP%2Bprefix-w-explanation.), but in this question, the nums[i] range [0, 1000] is too large to use normal iteration, so we use prefix to optimize.\n```\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        mod = 10**9+7\n        n = max(nums)\n        dp = [0]*(n+1)\n        for j in range(nums[0]+1):\n            dp[j] = j+1\n        for i in range(1, len(nums)):\n            curr = [0]*(n+1)\n            for j in range(nums[i]+1):\n                k = min(j, nums[i-1], j+nums[i-1]-nums[i])\n                if k >= 0:\n                    curr[j] += dp[k]\n            for j in range(1, n+1):\n                curr[j] += curr[j-1]\n                curr[j] %= mod\n            dp = curr\n        return dp[n]\n```
['Dynamic Programming', 'Python', 'Python3']