Video Explanation - Journey from O(N*X*X*X) --> O(N*X*X) --> O(N*X)
Explanation\n\nClick here for the video\n\n# Code\n\nconst int N = 2001;\nconst int M = 1e9+7;\n\nclass Solution {\npublic:\n    int countOfPairs(vector<int>& n
# Explanation\n\n[Click here for the video](https://youtu.be/37S9Debk8Bg)\n\n# Code\n```\nconst int N = 2001;\nconst int M = 1e9+7;\n\nclass Solution {\npublic:\n    int countOfPairs(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> dp(N, 1);   // dp[i+1]\n        \n        for (int i = n-1; i >= 0; i --) {\n            vector<int> new_dp (N, 0);\n            \n            vector<int> prefix (N, 0);\n            prefix[0] = dp[0];\n            for (int j = 1; j < N; j ++) prefix[j] = (prefix[j-1] + dp[j]) % M;\n            \n            for (int prv1 = 0; prv1 <= 2000; prv1 ++) {\n                int prv2 = (i > 0)? nums[i-1]-prv1 : 1e9;\n                if (prv2 < 0) break;\n                \n                int l = max(prv1, nums[i] - prv2);\n                int r = nums[i];\n                \n                if (l <= r) new_dp[prv1] = (prefix[r] - (l > 0? prefix[l-1] : 0) + M) % M;\n            }\n            dp = new_dp;\n        }        \n        return dp[0];\n    }\n};\n```
['C++']