Easy to understand DP
Intuition\n Describe your first thoughts on how to solve this problem. \nUsing DP and prefix sum \n\n# Approach\n Describe your approach to solving the problem.
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUsing DP and prefix sum \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n`dp[i][j]` means for the position `j`, we choose `i` as the number in `arr`. \n\nHere,\n- $0\\leq i\\leq M$\n- $0\\leq j <n$\n\nTake `nums = [2,3]` as an example, the final answer should be $6$ because `arr1` can be:\n1. `[0,1]`\n2. `[0,2]`\n3. `[1,2]`\n4. `[0,3]`\n5. `[1,3]`\n6. `[2,3]`\n\nFor `j == 1`, the possible number in `arr` is $1$, $2$, and $3$. When `i == 2`, the cases ending with `1` are always valid (i.e. `[0, 1]` here). Also, we need to add `dp[i - d][j - 1]` because this is the largest value we can have for the previous digit.\n\nSimilarly, when `j == 1` and `i == 3`, the cases ending with `2` are alwyas valid as well (i.e. `[0, 2]` and `[1, 2]` here).\n\n# Complexity\n- Time complexity: $O(Mn)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(Mn)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n Can be $O(M)$ by replace `dp` with two $(1, M + 1)$ lists.\n\n# Code\n```\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n        MOD = 1_000_000_007\n        n = len(nums)\n        M = max(nums)\n        dp = [[0]*n for _ in range(M + 1)]\n\n        for i in range(M + 1):\n            dp[i][0] = 1\n        \n        for j in range(1, n):\n            d = max(0, nums[j] - nums[j - 1])\n            for i in range(d, nums[j] + 1):\n                dp[i][j] = (dp[i - 1][j] + dp[i - d][j - 1]) % MOD\n        \n        return sum(dp[i][-1] for i in range(M + 1)) % MOD\n                \n                \n\n```
['Python3']