Math for DP Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nthis should be prefix sum + dynamic programming!\n\n# Approach\n Describe your approach
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nthis should be prefix sum + dynamic programming!\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nmathmathmathmathmath\n\nwe first get the values in arr2 by finding `b = i - a` where `a = max(a, i - b)`\n\nwe then perform combi on `min(arr2) + len(arr2)` and `len(arr2)`\nmod as the question asks and we achieve the ultimate #proofbyAC with math!\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n```\nfrom math import comb\n\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        MOD = 10**9 + 7\n        a = 0; b = nums[0]\n        arr1 = [a]; arr2 = [b]\n\n        for i in nums[1:]:\n            a = max(a, i - b); b = i - a\n            arr1.append(a)\n            arr2.append(b)\n        \n        t = min(arr2)\n        \n        if t < 0: return 0\n\n        n = len(arr2)\n        \n        return comb(t + n, n) % MOD\n```
['Python3']