[Java/C++/Python] DP, O(n)
Explanation\ndp[i][j] means the count of first i + 1 pairs and arr1[i] = j.\n\nSince arr1[0] can be any value that 0 <= arr1[0] <= A[0],\nwe initilize d[0][j] =
# **Explanation**\n`dp[i][j]` means the count of first `i + 1` pairs and `arr1[i] = j`.\n\nSince arr1[0] can be any value that `0 <= arr1[0] <= A[0]`,\nwe initilize `d[0][j] = 1`\n\nFrom the problem we have\n`A[i - 1] - arr1[i - 1] >= A[i] - arr1[i]`\n\nThat is:\n`arr1[i - 1] + A[i] - A[i - 1] <= arr1[i]`\n\nSo we can have\n`arr1[i - 1] + d <= arr1[i]`,\nwhere `d = max(0, A[i] - A[i - 1])`,\n\nThus we can have the dp equation:\n`dp[i][j] = dp[i][j - 1] + dp[i - 1][j - d]`\n\nFinally we return `sum(dp[n - 1])`\n\nBecause `dp[i]` only depends on `dp[i - 1]`,\nwe can optimize it to 1 dimention dp with `O(n)` space\n<br>\n\n# **Complexity**\nTime `O(nm)`, where `m = max(A) + 1`\nSpace `O(m)`\n<br>\n\n**Java**\n```java\n    public int countOfPairs(int[] A) {\n        int n = A.length, m = 1001, mod = 1000000007, dp[] = new int[m];\n        Arrays.fill(dp, 1);\n\n        for (int i = 1; i < n; ++i) {\n            int d = Math.max(0, A[i] - A[i - 1]), dp2[] = new int[m];\n            for (int j = d; j < A[i] + 1; ++j) {\n                dp2[j] = ((j > 0 ? dp2[j - 1] : 0) + dp[j - d]) % mod;\n            }\n            dp = dp2;\n        }\n\n        int res = 0;\n        for (int j = 0; j <= A[n - 1]; ++j)\n            res = (res + dp[j]) % mod;\n        return res;\n    }\n```\n\n**C++**\n```cpp\n    int countOfPairs(vector<int>& A) {\n        int n = A.size(), m = 1001, mod = 1e9 + 7;\n        vector<int> dp(m, 1);\n\n        for (int i = 1; i < n; ++i) {\n            int d = max(0, A[i] - A[i - 1]);\n            vector<int> dp2(m, 0);\n            for (int j = d; j < A[i] + 1; ++j) {\n                dp2[j] = ((j > 0 ? dp2[j - 1] : 0) + dp[j - d]) % mod;\n            }\n            swap(dp, dp2);\n        }\n\n        int res = 0;\n        for (int j = 0; j <= A[n - 1]; ++j)\n            res = (res + dp[j]) % mod;\n        return res;\n    }\n```\n\n**Python**\n```py\n    def countOfPairs(self, A: List[int]) -> int:\n        mod = 10 ** 9 + 7\n        n, m = len(A), max(A) + 1\n        dp, dp2 = [1] * m, [0] * m\n        for i in range(1, n):\n            d = max(0, A[i] - A[i - 1])\n            for j in range(d, A[i] + 1):\n                dp2[j] = (dp2[j - 1] + dp[j - d]) % mod\n            dp, dp2 = dp2, [0] * m\n        return sum(dp) % mod\n```\n\n**Short Python**\n```py\n    def countOfPairs(self, A: List[int]) -> int:\n        dp = [1] * (A[0] + 1)\n        for a,b in pairwise(A):\n            dp = list(accumulate([0] * (b - a) + dp))[:b + 1]\n        return sum(dp) % (10 ** 9 + 7)\n```\n<br>\n\n\n# **Solution 2: Combinations**\nSolution 0 is a 2D dp.\nSolution 1 is a simplified 1D dp.\n\nwe notice the result is a `n`-times accumulated number,\nwhich is also a combination number.\n\nFrom the latest python solution,\nwe can see the final length of list is `A[n - 1]`,\nWe only need to calculate the prefix zeros,\nwhich is the sum of increases.\n\nFrom the understanding of math,\nit\'s same as the number of increasing sequence `a` that\n`a1 <= a2 <=  .... <= an <= v`\n\nTime `O(n + m)` for `comb` in Python, need extra `logmod` for general calculation.\nSpace `O(1)`\n\n**Python**\n```py\n    def countOfPairs(self, A: List[int]) -> int:\n        v = A[-1] - sum(max(b - a, 0) for a,b in pairwise(A))\n        return comb(len(A) + v, v) % (10 ** 9 + 7) if v > 0 else 0\n```\n\n
['C', 'Python', 'Java']