Super Fast
AC 63 ms. This is the idea how to go from cubic to quadratic.\n\nIf nums[i - 1] >= nums[i], then:\n- dp[i][0] = dp[i - 1][0]\n- dp[i][1] = dp[i - 1][0] + dp[i -
AC 63 ms. This is the idea how to go from cubic to quadratic.\n\nIf `nums[i - 1] >= nums[i]`, then:\n- `dp[i][0] = dp[i - 1][0]`\n- `dp[i][1] = dp[i - 1][0] + dp[i - 1][1]`\n- ...\n- `dp[i][nums[i]] = dp[i - 1][0] + ... + dp[i - 1][nums[i]]`.\n\nTo compute `sum(dp[i - 1][0..n])`, we just accumulate all previous values in `sum` as we go.\n\nNow, if `nums[i - 1] < nums[i]`, we need to offset the initial index by `nums[i] - nums[i - 1]`:\n- `dp[i][0] = 0`\n- ...\n- `dp[i][nums[i] - nums[i - 1]] = dp[i - 1][0]`\n- `dp[i][nums[i] - nums[i - 1] + 1] = dp[i - 1][0] + dp[i - 1][1]`\n- ...\n- `dp[i][nums[i]] = dp[i - 1][0] + ... + dp[i - 1][nums[i] - nums[i - 1]]`\n\n**C++**\n```cpp\nint countOfPairs(vector<int>& nums) {\n    int dp[2][1001], mod = 1000000007, sz = nums.size();\n    fill_n(begin(dp[1]), nums[0] + 1, 1);\n    for (int i = 1; i < sz; ++i) {\n        for (int n = 0, sum = 0; n <= nums[i]; ++n) {\n            if (int off = n + min(0, nums[i - 1] - nums[i]); off >= 0)\n                sum = (sum + dp[i % 2][off]) % mod;\n            dp[!(i % 2)][n] = sum;\n        }\n    }\n    return accumulate(begin(dp[sz % 2]), begin(dp[sz % 2]) + nums.back() + 1, 0, \n        [&](int s, int n){ return (s + n) % mod; });\n}\n```
['C']