Simple Explanation (C++) | Optimised DP
Intuition\nLooks like a dynamic programming problem.\n# Approach\nIn part I of this we were updating the dp for i th index for allsatisfying values based on the
# Intuition\nLooks like a dynamic programming problem.\n# Approach\nIn part I of this we were updating the dp for i th index for allsatisfying values based on the values of index i-1.\nBut we cannot do that here because it would exceed time limit. \nUpon observation, we see that always a range is updated based on the\nvalue of previous index. We can optimise range updates by using difference array. If we want to update range [a,b] with value c we add value c at index a and -c at index b+1. Then we take prefix sum to get the original array.\n# Complexity\n- Time complexity: $$O(max(nums)*n)$$\n- Space complexity: $$O(1002*n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int countOfPairs(vector<int>& nums)\n    {\n        int n = nums.size(), mod = 1e9+7;\n        vector<vector<long long>> dp(n,vector<long long> (1002,0));\n        for(int j=0; j<=nums[0]; j++)\n            dp[0][j] = 1;\n        for(int i=1; i<n ;i++)\n        {\n            for(int j=0; j<=nums[i-1]; j++)\n            {\n                if(nums[i] < j) break;\n                int cur = j, prev1 = j, prev2 = nums[i-1] - j;\n                if(nums[i] - j > prev2) cur = nums[i]-prev2;\n                dp[i][cur] += dp[i-1][prev1];\n                dp[i][nums[i]+1] -= dp[i-1][prev1];\n                dp[i][nums[i]] %= mod; \n            }\n            dp[i][0] += mod;\n            dp[i][0] %= mod;\n            for(int j=1; j<=1001; j++)\n            {\n                dp[i][j] += dp[i][j-1];\n                dp[i][j] += mod;\n                dp[i][j] %= mod;\n            }\n        }\n        return (accumulate(dp[n-1].begin(),dp[n-1].end(),0LL)%mod + mod)%mod;\n    }\n};\n```
['Math', 'Dynamic Programming', 'Counting', 'Prefix Sum', 'C++']