Memo -> Tabulation -> optimisation for time complexity -> optimisation for space complexity
Memo Code \n\nclass Solution {\npublic:\n    const int mod = 1000000007;\n    long solve(int last, int idx, vector<int> &nums, int n,vector<vector<long>> &dp){\
# Memo Code \n```\nclass Solution {\npublic:\n    const int mod = 1000000007;\n    long solve(int last, int idx, vector<int> &nums, int n,vector<vector<long>> &dp){\n        if(idx == n){\n            return 1;\n        }\n        if(dp[last][idx] != -1) return dp[last][idx];\n        if(idx==0){\n            long long ans = 0;\n            for(int i=0;i<=nums[0];i++){\n                ans += solve(i,idx+1, nums, n,dp);\n                ans%=mod;\n            }\n            return dp[last][idx] = ans%mod;;\n        }\n        int l_inc = last;\n        int l_dec = nums[idx-1]-last;\n        long long ans = 0;\n        for(int i=max(l_inc,nums[idx]-l_dec);i<=nums[idx];i++){\n            ans += solve(i, idx+1, nums,n,dp);\n            ans%=mod;\n        }\n        return dp[last][idx] = ans%mod;;\n    }\n    int countOfPairs(vector<int>& nums) {\n        int n = nums.size();\n        vector<vector<long>> dp(50+1, vector<long>(n,-1));\n        return solve(0,0,nums,n,dp)%mod;;\n    }\n};\n```\n# Tabulation Code without optimization\n```\nclass Solution {\npublic:\n    const int mod = 1000000007;\n    \n    int countOfPairs(vector<int>& nums) {\n        int n = nums.size();\n        vector<vector<long>> dp(1000+1, vector<long>(n+1,-1));\n\n        for (int last = 0; last <= 1000; last++) {\n            dp[last][n] = 1;\n        }\n        for(int idx = n-1;idx>=0;idx--)\n        for (int last = 0; last <= 1000; last++) {\n            if(idx==0){\n                long long ans = 0;\n                for(int i=0;i<=nums[0];i++){\n                    ans += dp[i][idx+1];\n                    ans%=mod;\n                }\n                dp[last][idx] = ans;\n            }else{\n                int l_inc = last;\n                int l_dec = nums[idx-1]-last;\n                long long ans = 0;\n                for(int i=max(l_inc,nums[idx]-l_dec);i<=nums[idx];i++){\n                    ans += dp[i][idx+1];\n                    ans%=mod;\n                }\n                dp[last][idx] = ans%mod;\n            }\n        }\n        return dp[0][0];\n    }\n};\n```\n\n# Tabulation Code with optimization but still give memory limit exceeded\n```\nclass Solution {\npublic:\n    const int mod = 1000000007;\n    \n    int countOfPairs(vector<int>& nums) {\n        int n = nums.size();\n        vector<vector<long>> dp(1000+1, vector<long>(n+1,-1));\n        vector<vector<long>> prefixSum(1000+1, vector<long>(n+1,0));\n        \n        // Base case\n        for (int last = 0; last <= 1000; last++) {\n            dp[last][n] = 1;\n            if(last) prefixSum[last][n] = prefixSum[last-1][n]+1;\n            else prefixSum[last][n]=1;\n        }\n        \n        // Fill the dp table from right to left\n        for(int idx = n-1; idx >= 0; idx--) {\n            // Calculate prefix sum for the current column\n            for (int last = 0; last <= 1000; last++) {\n                if(last){\n                    prefixSum[last][idx+1] = prefixSum[last-1][idx+1] + dp[last][idx+1];\n                }else{\n                    prefixSum[last][idx+1] = dp[last][idx+1];\n                }\n                prefixSum[last][idx+1]%= mod;\n            }\n            \n            for (int last = 0; last <= 1000; last++) {\n                if(idx == 0){\n                    // For the first element, sum up all possibilities\n                    dp[last][idx] = prefixSum[nums[0]][idx+1];\n                } else {\n                    int l_inc = last;\n                    int l_dec = nums[idx-1] - last;\n                    int st = max(l_inc, nums[idx] - l_dec);\n                    int end = nums[idx];\n                    \n                    if (st <= end) {\n                        if(st){\n                            dp[last][idx] = (prefixSum[end][idx+1] - prefixSum[st-1][idx+1] + mod)%mod;\n                        }else{\n                            dp[last][idx] = prefixSum[end][idx+1];\n                        }\n                    } else {\n                        dp[last][idx] = 0;\n                    }\n                }\n            }\n        }\n        \n        return dp[0][0];\n    }\n};\n```\n# Tabulation Code with optimization for memory too\n```\nclass Solution {\npublic:\n    const int mod = 1000000007;\n    \n    int countOfPairs(vector<int>& nums) {\n        int n = nums.size();\n        int maxNum = *max_element(nums.begin(), nums.end());\n        // maxNum so that do not have to take till 1000\n        vector<vector<long>> dp(maxNum + 1, vector<long>(n + 1, 0));\n        // as we do not need to store for all idx\n        vector<long> prefixSum(maxNum + 2, 0);\n\n        \n        // Base case: when idx == n\n        for (int last = 0; last <= maxNum; last++) {\n            dp[last][n] = 1;\n        }\n        \n        // Fill the dp table\n        for (int idx = n - 1; idx >= 0; idx--) {\n            // Calculate prefix sum for the current column\n            prefixSum[0] = 0;\n            for (int i = 1; i <= maxNum + 1; i++) {\n                prefixSum[i] = (prefixSum[i-1] + dp[i-1][idx+1]) % mod;\n            }\n            \n            for (int last = 0; last <= maxNum; last++) {\n                if (idx == 0) {\n                    dp[last][idx] = prefixSum[nums[0] + 1];\n                } else {\n                    int l_inc = last;\n                    int l_dec = nums[idx - 1] - last;\n                    int st = max(l_inc, nums[idx] - l_dec);\n                    int end = nums[idx];\n                    \n                    if (st <= end) {\n                        dp[last][idx] = (prefixSum[end + 1] - prefixSum[st] + mod) % mod;\n                    } else {\n                        dp[last][idx] = 0;\n                    }\n                }\n            }\n        }\n        \n        return dp[0][0];\n    }\n};\n```\n
['C++']