[Math] A different way to simplify this problem
Observation\n\nLet\'s consider arr1 first: there should be a "base array" which is the "common part" for all valid arr1s.\n\nUse [2,3,2] as an example, the "bas
# Observation\n\nLet\'s consider arr1 first: there should be a "base array" which is the "common part" for all valid arr1s.\n\nUse `[2,3,2]` as an example, the "base array" for arr1 is `[0,1,1]`. If you check all possible arr1s, their "common part" is `[0,1,1]`. \n\nThis array can be calculated greedily. First element should always be 0, second element is 1 because 3-2=1, third element is still 1 because of the condition that `arr1[n-2] <= arr1[n-1]`.\n\nUsing the same method, we can also calculate the "base array" for arr2, which is `[1,1,0]`.\n\nThen with `nums - base1 - base2` we have a new array `[1,1,1]`. We can call it `newNums`. We just need to distribute the numbers in `newNums` to `base1` and `base2` to construct `arr1` and `arr2`. Here all elements in `newNums` are the same (`1`). It is a relatively simple problem to calculate the way of distribution.  \n\nThe question is, is it true for any input `nums` that the `newNums` has all same elements? It is true and can be proved by induction.\n\n----\n\nProof:\n\nSay input is `nums = [a0,a1,...,a_(n-1),a_n]`, the "new array" is `newNums`. Assume all elements in `newNums` are the same (call it `b`). Then we add a new number `a_(n+1)` to `nums`, and there should be a new number in `newNums` which is `b\'`. We just need to prove `b == b\'`.\n\nIf `a_n <= a_(n+1)`, then `base1_(n+1) = base1_n + a_(n+1) - a_n`, and `base2_(n+1) = base2_n = 0`. Then `b\' = a_(n+1) - base1_(n+1) = a_(n+1) - base1_n - a_(n+1) + a_n = a_n - base1_n = b`.\n\nIf `a_n > a_(n+1)`, then `base1_(n+1) = base1_n`. And `base2_(n+1) = 0`, and `base2_n = a_n - a_(n+1)`. Then `b\' = a_(n+1) - base1_(n+1) - base2_(n+1) = a_(n+1) - base1_n`, and `b = a_n - base1_n - base2_n = a_n - base1_n - a_n + a_(n+1) = a_(n+1) - base1_n = b\'`.\n\nProved. \n\n----\n\nThen the problem becomes easier. We can just apply some basic DP to solve it.\n\n# Code\n```\n\n/*\nRuntime 36 ms\nBeats 100.00% of users with Java\nMemory 44.2 MB\nBeats 100.00% of users with Java\n*/\n\nclass Solution {\n    private final static int MOD = (int) (1e9 + 7);\n\n    public int countOfPairs(int[] nums) {\n        int base = 0;\n        for (int i = 1; i < nums.length; i++) {\n            if (nums[i] > nums[i - 1]) {\n                base += nums[i] - nums[i - 1];\n            }\n        }\n\n        int maxRange = nums[nums.length - 1] - base;\n        if (maxRange < 0) {\n            return 0;\n        }\n        if (maxRange == 0) {\n            return 1;\n        }\n\n        int[] next = new int[nums.length];\n        Arrays.fill(next, 1);\n        int[] curr = new int[nums.length];\n\n        for (int i = 1; i <= maxRange; i++) {\n            curr[curr.length - 1] = i + 1;\n\n            for (int j = curr.length - 2; j >= 0; j--) {\n                curr[j] = curr[j + 1] + next[j + 1];\n                curr[j] %= MOD;\n            }\n\n            for (int j = 0; j < next.length; j++) {\n                next[j] += curr[j];\n                next[j] %= MOD;\n            }\n        }\n\n        return curr[0];\n    }\n}\n```
['Math', 'Java']