Clean C++ Solution (Prefix Sum + DP)
Intuition\n Describe your first thoughts on how to solve this problem. \ndp[i][j] = dp[i+1][k] (max(j,nums[i]-(nums[i-1]-j))<= k <=(nums[i])\n\n# Approach\n Des
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\ndp[i][j] = dp[i+1][k] (max(j,nums[i]-(nums[i-1]-j))<= k <=(nums[i])\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nState Definition:\ndp[ind][pre] stores the number of valid sequences starting at index ind with the previous value pre.\n\nTransition:\nTo avoid iterating over a range of values for each state, we use prefix sums to quickly calculate the sum of valid transitions for the next state.\n\n# Complexity\n- Time complexity: O(N*1000)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N*2000)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    const int mod = 1e9+7;\n\n    int countOfPairs(vector<int>& nums) {\n        int n = nums.size();\n        vector<vector<int>> dp(n+1, vector<int>(1001, 0));\n        vector<vector<int>> prefix(n+1, vector<int>(1001,0));\n\n        for (int i = 0; i <= nums.back(); i++) {\n            dp[n][i] = 1;\n            prefix[n][i] = 1;\n            if(i>0){\n                prefix[n][i]+=prefix[n][i-1];\n                prefix[n][i]%=mod;\n            }\n        }\n\n        for (int ind = n - 1; ind >= 0; ind--) {\n            for (int pre = 0; pre <= 1000; pre++) {\n                int res = 0;\n\n                int start = pre;\n                int end = nums[ind];\n                if (ind > 0) {\n                    start = max(pre, nums[ind] - (nums[ind-1] - pre));\n                }\n\n                if(start>end){\n                    start=end+1;\n                }\n\n                if(start==0){\n                    res=prefix[ind+1][end];\n                } else {\n                    res=(prefix[ind+1][end]-prefix[ind+1][start-1])%mod;\n                    if(res<0){\n                        res+=mod;\n                    }\n                }\n\n                dp[ind][pre] = res;\n                prefix[ind][pre] = res;\n                if(pre>0){\n                    prefix[ind][pre]+=prefix[ind][pre-1];\n                    prefix[ind][pre]%=mod;\n                }\n            }\n        }\n\n        return dp[0][0];\n    }\n};\n```
['Dynamic Programming', 'Prefix Sum', 'C++']