C++ ,memorisation to iteration
Intuition\ntake the recurrsive approach \n\n\nclass Solution {\npublic: \n    long long dp[2001][1001];\n    long long solver(int i, int n, int v1, int v2,vecto
# Intuition\n**take the recurrsive approach **\n\n```\nclass Solution {\npublic: \n    long long dp[2001][1001];\n    long long solver(int i, int n, int v1, int v2,vector<int>& nums) {\n        if (i == n)\n            return 1;\n\n        long long ans = 0;\n\n        if(dp[i][v1]!=-1)\n        return dp[i][v1];\n\n        for (int j = nums[i]; j >= v1  && nums[i] - j <= v2; j--) {\n            ans = (ans +  solver(i + 1, n, j, nums[i] - j,nums)) % (1000000007);\n        }\n\n        return dp[i][v1] =  ans;\n    }\n    long long countOfPairs(vector<int>& nums) {\n        int n = nums.size();\n        long long ans = 0;\n        memset(dp,-1,sizeof(dp));\n        for (int v1 = 0; v1 <= nums[0]; v1++)\n            ans = (ans + solver(1, n, v1, nums[0] - v1,nums)) % (1000000007);\n\n        return ans %(1000000007);\n    }\n};\n\n```\n\n**take the recurrsive to reverse direction**\n\n```\nclass Solution {\npublic: \n    long long dp[2001][51];\n    long long solver(int i, int n, int v1,vector<int>& nums) {\n        if (i == 0)\n            return 1;\n        int v2 = nums[i]-v1;\n        long long ans = 0;\n\n        if(dp[i-1][v1]!=-1)\n        return dp[i-1][v1];\n\n        for (int j = nums[i-1]; j >= v1  && nums[i-1] - j <= v2; j--) {\n            ans = (ans +  solver(i - 1, n, j,nums)) % (1000000007);\n        }\n\n        return dp[i-1][v1] =  ans;\n    }\n    long long countOfPairs(vector<int>& nums) {\n        int n = nums.size();\n        long long ans = 0;\n        memset(dp,-1,sizeof(dp));\n        for (int v1 = 0; v1 <= nums[n-1]; v1++)\n            ans = (ans + solver(n-1, n, v1,nums)) % (1000000007);\n\n        return ans %(1000000007);\n    }\n};\n```\n\n**convert to bottom up**\n\n```\nclass Solution {\npublic: \n    long long dp[2001][1001];\n\n    long long countOfPairs(vector<int>& nums) {\n        int n = nums.size();\n        memset(dp, 0, sizeof(dp));\n\n        for (int v1 = 0; v1 <= nums[0]; v1++) {\n            dp[0][v1] = 1;  \n        }\n\n        for (int i = 1; i < n; i++) {\n            for (int v1 = 0; v1 <= nums[i]; v1++) {\n                long long ans = 0;\n                int v2 = nums[i] - v1;\n                 for (int j = nums[i-1]; j >= v1  && nums[i-1] - j <= v2; j--)\n               {\n                    ans = (ans + dp[i - 1][j]) % 1000000007;\n                }\n\n                dp[i][v1] = ans;\n            }\n        }\n\n\n        long long ans = 0;\n        for (int v1 = 0; v1 <= nums[n - 1]; v1++) {\n            ans = (ans + dp[n - 1][v1]) % 1000000007;\n        }\n\n        return ans;\n    }\n};\n```\n\n**Reform this loop**\n```\n  for (int j = nums[i-1]; j >= v1  && nums[i-1] - j <= v2; j--)\n               {\n                    ans = (ans + dp[i - 1][j]) % 1000000007;\n                }\n```\n**to**\n\n```\n  for (int j = max(v1,  nums[i - 1] - nums[i] + v1); j <=  nums[i - 1]; j++) {\n                    ans = (ans + dp[i - 1][j]) % 1000000007;\n                }\n```\n\n\n**observe that this loop is just prefix sum**\n\n```\nclass Solution {\npublic: \n    \n    long long countOfPairs(vector<int>& nums) {\n        long long dp[2001][1001];\n        long long pre[2001][1001];\n        long long mod = 1000000007;\n        int n = nums.size();\n        memset(dp, 0, sizeof(dp));\n\n        for (int v1 = 0; v1 <= nums[0]; v1++) {\n            dp[0][v1] = 1;  \n            pre[0][v1] = v1+1;\n        }\n\n        for (int i = 1; i < n; i++) {\n            for (int v1 = 0; v1 <= nums[i]; v1++) {\n                long long ans = 0;\n                int v2 = nums[i] - v1;\n                int m = max(v1,  nums[i - 1] - nums[i] + v1);\n                if(m<=nums[i - 1])\n                    ans  =  (mod + pre[i-1][nums[i - 1]]%mod - (m==0?0:pre[i-1][m-1])%mod)%mod;\n              \n                pre[i][v1] = (v1==0?0:pre[i][v1-1]) + ans;\n                dp[i][v1] = ans;\n            }\n        }\n\n\n        long long ans = 0;\n        for (int v1 = 0; v1 <= nums[n - 1]; v1++) {\n            ans = (ans + dp[n - 1][v1]) % mod;\n        }\n\n        return ans;\n    }\n};\n\n```\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\nO(N*N)\n\n- Space complexity:\nO(N*N)\n\n# Code\n```cpp []\nclass Solution {\npublic: \n    \n    long long countOfPairs(vector<int>& nums) {\n        long long dp[2001][1001];\n        long long pre[2001][1001];\n        long long mod = 1000000007;\n        int n = nums.size();\n        memset(dp, 0, sizeof(dp));\n\n        for (int v1 = 0; v1 <= nums[0]; v1++) {\n            dp[0][v1] = 1;  \n            pre[0][v1] = v1+1;\n        }\n\n        for (int i = 1; i < n; i++) {\n            for (int v1 = 0; v1 <= nums[i]; v1++) {\n                long long ans = 0;\n                int v2 = nums[i] - v1;\n                int m = max(v1,  nums[i - 1] - nums[i] + v1);\n                if(m<=nums[i - 1])\n                    ans  =  (mod + pre[i-1][nums[i - 1]]%mod - (m==0?0:pre[i-1][m-1])%mod)%mod;\n              \n                pre[i][v1] = (v1==0?0:pre[i][v1-1]) + ans;\n                dp[i][v1] = ans;\n            }\n        }\n\n\n        long long ans = 0;\n        for (int v1 = 0; v1 <= nums[n - 1]; v1++) {\n            ans = (ans + dp[n - 1][v1]) % mod;\n        }\n\n        return ans;\n    }\n};\n\n```
['C++']