C++ O(N*M) time O(M) space with step by step visualization
Starting with example 1:nums = [2, 3, 2]Lets first see what can we fill the last index with; it could be:Now calculate a dp array dp0 as suchNow onto the second
Starting with example 1:

`nums = [2, 3, 2]`

Lets first see what can we fill the **last** index with; it could be:

```
arr1 = [0] or [1] or [2]
arr2 = [2] or [1] or [0]
```

Now calculate a dp array `dp0` as such
```
dp0[0] = 1; // how many arr1 = [0, ...] and arr2 = [2, ...] are legal pairs? (We are at the beginning so its obvious every count is exactly 1; "..." is empty)
dp0[1] = 1; // ditto
dp0[2] = 1;
```

Now onto the second last element of `nums`; what can we put in `arr1` and `arr2`?
```
arr1 = [0, ...] or [1, ...] or [2, ...] or [3, ...]
arr2 = [3, ...] or [2, ...] or [1, ...] or [0, ...]
```

Take 
```
arr1 = [0, ...]
arr2 = [3, ...]
```
for example, **whatever we can append to `arr1`, its first element must be greater or equal to 0**;
same for `arr2`: **whatever we can append to `arr2`, its first element must be less or equal to 3**;

We can see that these are legal:
```
append_to_arr1 = [0] or [1] or [2] => [0, 0] or [0, 1] or [0, 2] 
append_to_arr2 = [2] or [1] or [0] => [3, 2] or [3, 1] or [3, 0]
```
In essense, transpose `append_to_arr1` and `append_to_arr2` to better visualize:
```
0 + 2 ---> every pair below this is legal
1 + 1
2 + 0
```
notice that this result is already in `dp0`.

Now calculate  `dp1`:
```
dp1[0] = 3; // how many arr1 = [0, ...] and arr2 = [3, ...] are legal pairs?
dp1[1] = 2; // ditto
dp1[2] = 1;
dp1[3] = 0; // impossible
```

It may seem like you need to iterate through `dp0` and check if `i >= 0 && j <= 3 && i + j == 2`, only then we increment `dp1[0]` by `dp0[i]`,
but it turns out we can just calculate a suffix sum to acquire the answer in O(1).

We'll show this with another example:
`nums = [3, 5]`

Starting from last index of `nums`
```
arr1 = [0] or [1] or [2] or [3] or [4] or [5]
arr2 = [5] or [4] or [3] or [2] or [1] or [0]
```
```
dp0[0] = 1; // how many arr1 = [0, ...] and arr2 = [5, ...] are legal pairs?
dp0[1] = 1; // ditto
dp0[2] = 1;
...
```

Second last index:
```
arr1 = [0, ...] or [1, ...] or [2, ...] or [3, ...]
arr2 = [3, ...] or [2, ...] or [1, ...] or [0, ...]
```

for
```
arr1 = [0, ...]
arr2 = [3, ...]
```
, these are legal:
```
append_to_arr1 = [2] or [3] or [4] or [5]
append_to_arr2 = [3] or [2] or [1] or [0]
```
i.e.
```
0 + 5
1 + 4
2 + 3 ---> every pair below this is legal; lets denote it as a + b
3 + 2
4 + 1
5 + 0
```

Notice that given current `x = 0, y = 3`, we can get `a` as such:
`a = max(x, 5 - y)`
because remember what we've established:
**append_to_arr1's first element must be greater or equal to 0** which is `a >= x`, and also
**append_to_arr2's first element must be less or equal to 3**, which is `b <= y` -> `5 - a <= y` -> `a >= 5 - y`;
Combining `a >= x` & `a >= 5 - y`, therefore `max(x, 5 - y) = max(0, 2) = 2` is the minimum `a` that satisfies both constraints.

Now we get `min(a) = 2`, we merely need the sum of number of legal pairs such that `[i, j] where i + j = 5 and i >= 2` i.e. how many pairs including and below `2 + 3`?
We can just calculate the suffix sum of `dp0` to quickly get this number.

Finally, when we finished calculating each element for `dp1`, just swap it with `dp0` and continue;
once we are done with `nums[0]`, `dp0[0]` is our answer.

Code:
```
class Solution {
public:
    int countOfPairs(const std::vector<int>& nums)
    {
        const int N = static_cast<int>(nums.size());
        constexpr int mod = 1000000007;

        int dp0_size = nums.back() + 1;
        std::vector<int> dp0(dp0_size);
        for (int i = 0, v = dp0_size; i < dp0_size; i++) {
            dp0[i] = v--;
        } // the "We are at the beginning so its obvious every count is exactly 1; "..." is empty" part
        for (int i = N - 2; i >= 0; i--) {
            const int dp1_size = nums[i] + 1;
            std::vector<int> dp1(dp1_size); // for 0+i, 1+(i-1), 2+(i-2)...
            for (int j = 0; j < dp1_size; j++) {
                const int x = j;
                const int y = nums[i] - j;
                const int a = std::max(x, dp0_size - y - 1); // every pair below this is legal
                if (a < dp0_size) { // a could exceed previous num, resulting in 0 legal pairs
                    dp1[j] = dp0[a];
                } else {
                    dp1[j] = 0;
                }
            }
            for (int j = dp1_size - 2; j >= 0; j--) { // calculate suffix sum
                dp1[j] += dp1[j + 1];
                dp1[j] %= mod;
            }
            dp0.swap(dp1);
            dp0_size = dp1_size;
        }

        return dp0.front();
    }
};
```
Time complexity: O(N * M)
Space Complexity: O(M)

['Dynamic Programming', 'C']