Simple DP + Prefix Sum Optimization || Easy to understand || CPP || Beats 100%
Complexity\n- Time complexity:O(n * m)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(n * m)\n Add your space complexity here, e.g. O(n) \n
# Complexity\n- Time complexity:$$O(n * m)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n * m)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int countOfPairs(vector<int>& nums) {\n        nums.insert(nums.begin(), 1000);\n        int n = nums.size();\n        vector<vector<long long>> dp(n+1, vector<long long>(1005, 0));\n        long long mod = 1e9 + 7;\n        for(int i=0; i<=1000; i++) dp[n][i] = 1;\n        for(int i=n-1; i>=1; i--){\n            vector<long long> pref(nums[i] + 1, 0);\n            for(int val=nums[i]; val >= 0; val--){\n                int xt = nums[i] - val;\n                pref[xt] = dp[i+1][val];\n                if(xt > 0) pref[xt] = (pref[xt] + pref[xt - 1]) % mod;\n            }\n            for(int val=0; val<=1000; val++){\n                int val2 = nums[i-1] - val;\n                int val3 = nums[i] - val;\n                int mini = min(val2, val3);\n                if(mini >= 0) dp[i][val] = pref[mini];\n            }\n        }\n        return dp[1][0];\n    }\n};\n```
['C++']