table dp + prefix sum
python cache made me dumb in solving such table dp questions ... \n\nkey point:\n\ndp[i][s] (number of states at index i-1 and s in the increasing array) = sum(
python cache made me dumb in solving such table dp questions ... \n\nkey point:\n\ndp[i][s] (number of states at index i-1 and s in the increasing array) = sum(dp[i+1][t]) where s+max(0,nums[i]-nums[i-1]\uFF09t<=nums[-1]\n\nthe sum can be precalculated in the prefix sum manner\n\n\n# Code\n```\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        l = nums[-1]\n        n = len(nums)\n        dp = [[0 for j in range(l+1)] for i in range(n+1)]\n        dp[n] = [1 for j in range(l+1)]\n        for i in range(n-1,-1,-1):\n            if i > 0 :d = max(0,nums[i]-nums[i-1])\n            else:d = 0\n            if i > 0: ma = min(l,nums[i])\n            else: ma = l\n            currs = 0 \n            for t in range(l,-1,-1):\n                if t+d<=l: currs += dp[i+1][t+d]\n                if nums[i-1] >= t: dp[i][t] = currs % (10**9+7)                                        \n        return dp[0][0] % (10**9+7)\n```
['Python3']