js/dp solution/time:O(m*n)/space:O(m)/ for m is the max val
Intuition\n\nThe problem asks us to count the number of valid monotonic pairs (arr1, arr2) where:\n- arr1 is monotonically non-decreasing.\n- arr2 is monotonica
## Intuition\n\nThe problem asks us to count the number of valid monotonic pairs `(arr1, arr2)` where:\n- `arr1` is monotonically non-decreasing.\n- `arr2` is monotonically non-increasing.\n- `arr1[i] + arr2[i] = nums[i]` for all `i`.\n\nGiven the constraints, directly generating all possible pairs would be infeasible. Therefore, we employ a dynamic programming (DP) approach to efficiently count the valid pairs by transitioning through possible states.\n\n## Approach\n\n### Dynamic Programming Setup\n\nWe define a DP array `dp[i][j]` where:\n- `i` represents the current index in the `nums` array that we\'re processing.\n- `j` represents the value of `arr1[i]`.\n- `dp[i][j]` holds the number of valid pairs `(arr1, arr2)` where `arr1[i] = j`, `arr1` is non-decreasing up to index `i`, and `arr2[i] = nums[i] - j`.\n\n### Initial State\n\nWe start by initializing the DP array for the last element in `nums`:\n- For `i = n-1`, where `n` is the length of `nums`, we set `dp[n-1][j] = 1` for all `0 <= j <= nums[n-1]`.\n- This means that at the last index, any valid pair `(arr1[n-1], arr2[n-1])` can exist with `arr1[n-1] = j` and `arr2[n-1] = nums[n-1] - j`.\n\n### DP Transition\n\nWe process the array backwards from `i = n-2` to `i = 0`:\n- For each `i`, we calculate a new DP array `cur`, which represents the number of valid pairs for each possible value of `arr1[i]`.\n- To compute `dp[i][j]`, we accumulate values from the next state `dp[i+1][k]` where `k >= j` (since `arr1` is non-decreasing). For each valid `j`, we add up the valid transitions and store the results in `dp[i][j]`.\n\n### Example\n\nConsider `nums = [3, 2, 1]`:\n\n- **Initialization for `i = 2`:**\n  - `dp[2][0] = 1`, `dp[2][1] = 1`, since for `nums[2] = 1`, valid pairs are `(0, 1)` and `(1, 0)`.\n\n- **Transition to `i = 1`:**\n  - For `nums[1] = 2`, we consider possible values for `arr1[1]`:\n    - If `arr1[1] = 0`, then `arr2[1] = 2`. Accumulate values from `dp[2][j]` for `j >= 0` to update `dp[1][0]`.\n    - If `arr1[1] = 1`, do similar accumulation to update `dp[1][1]`.\n\n- **Final State at `i = 0`:**\n  - The final result is obtained by summing all values in `dp[0][j]`.\n\n### Complexity\n\n- **Time complexity**: `O(n * m)`, where `n` is the length of `nums` and `m` is the maximum value in `nums`, capped at 1000.\n- **Space complexity**: `O(m)`, due to the `dp` array that stores possible values for each `arr1[i]`.\n\n## Code\n\n```javascript\nconst MOD = 1e9 + 7;\n\nvar countOfPairs = function(nums) {\n    const n = nums.length;\n    let prev = new Array(1000).fill(0);\n\n    // Initialize for the last element in nums\n    for (let j = 0; j <= nums[n-1]; j++) {\n        prev[j] = 1;\n    }\n\n    // Process the array backwards\n    for (let i = n - 2; i >= 0; i--) {\n        let start = Math.max(0, nums[i + 1] - nums[i]);\n        const cur = new Array(1000).fill(0);\n        let acu = 0;\n\n        for (let j = nums[i + 1]; j >= start; j--) {\n            acu += prev[j];\n            acu = acu % MOD;\n            cur[j - start] = acu;\n        }\n\n        prev = cur;\n    }\n\n    // Sum up all possibilities\n    const rtn = prev.reduce((acu, cur) => (acu + cur) % MOD, 0);\n    return rtn;\n};\n```
['JavaScript']