DP, O(N*M*M) to O(N*M)
Intuition\nO(N MM) is straight forward.\n\nO(NM) needs to use prefix sum.\n\n\n# Code1 O(N MM)\npython3\nclass Solution:\n    def countOfPairs(self, nums: List[
# Intuition\n$$O(N *M*M)$$ is straight forward.\n\n$$O(N*M)$$ needs to use prefix sum.\n\n\n# Code1 $$O(N *M*M)$$\n```python3\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        n = len(nums)\n        \n        @cache\n        def dp(i, prv_1):\n            if i == n:\n                return 1\n            \n            # if arr1[i - 1] == prv_1\n            # then arr1[i] can only choose from [prv_1 ... nums[i]]\n            \n            result = 0\n\n            # arr2[i - 1] == nums[i - 1] - prv_1 based on the question\n            prv_2 = inf if i == 0 else nums[i - 1] - prv_1\n            \n            for num_1 in range(prv_1, nums[i] + 1):\n                # if arr1[i] == num_1\n                # then arr2[i] == nums[i] - num_1\n                num_2 = nums[i] - num_1\n                \n                # only add when it is valid\n                if num_2 <= prv_2:\n                    result += dp(i + 1, num_1)\n            \n            return result % MOD\n        \n        result = dp(0, 0)\n        dp.cache_clear()\n        return result\n```\n\n# Code2 $$O(N *M)$$\nFrom code1 we know that, for $$arr_1$$, $$dp(i, num_1) == \\sum dp(i - 1, prv_1)$$ where $$prv_1 \\le num_1$$\n\nFor $$arr_2$$, we have $$num_2 == nums[i]-num_1$$ and $$prv_2=nums[i-1]-prv_1$$\n\nWe need $$prv_2 \\ge num_2 == nums[i-1]-prv_1 \\ge nums[i]-num_1$$\n\nRearrange, we get $$prv_1\\le nums[i-1]-nums[i]+num_1$$\n\nTherefore, $$dp(i, num_1) == \\sum dp(i - 1, prv_1)$$ \nwhere $$prv_1 \\le min(num_1, nums[i-1]-nums[i]+num_1)$$\n\nThus, we need a prefix sum to quickly get the sum dp[i-1] from 0 to $$prv_1$$\n\n```python3\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        MOD = 10 ** 9 + 7\n        n = len(nums)\n        m = 1001\n        \n        # dp[i][j]: the valid monotonic pairs in nums[0...i]\n        # when arr1[i] == j\n        dp = [[0] * m for _ in range(n)]\n        \n        # at the beginning, arr1[0] can be any value\n        # from 0 to nums[0]\n        for num in range(nums[0] + 1):\n            dp[0][num] = 1\n        \n        for i in range(1, n):\n            presum = [0]\n            \n            for j in range(m):\n                presum.append((presum[-1] + dp[i - 1][j]) % MOD)\n            \n            \n            # prv_1 <= min(num_1, nums[i - 1] - nums[i] + num_1)\n            for num_1 in range(nums[i] + 1):\n                prv_1 = min(num_1, nums[i - 1] - nums[i] + num_1)\n                if prv_1 < 0:\n                    continue\n                # prv_1 + 1 is because presum has 1 offset\n                dp[i][num_1] = presum[prv_1 + 1]\n        \n\n        return sum(dp[-1]) % MOD\n```
['Dynamic Programming', 'Python3']