C++ | Easy DP Tabulation Table, Complement | Comments
Upvote if this helped\n# Complexity\n- Time complexity: O(nm) where n = the length of array and m = how high the numbers are in nums[i].\n\n- Space complexity: 
# Upvote if this helped\n# Complexity\n- Time complexity: $$O(n*m)$$ where n = the length of array and m = how high the numbers are in nums[i].\n\n- Space complexity: $$O(m^2)$$ = $$O(1000*1000)$$, there is probably also a better $$O(m)$$ space solution since the other number has to be the complement. Although, this way is a little bit more readable.\n\n# Code\n## Other TLE versions (including Memoization) are below if you need more understanding.\n```\n#include <bits/stdc++.h>\n#pragma GCC optimize ("Ofast")\n#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx2,tune=native")\nusing namespace std;\n#define all(x) x.begin(), x.end()\nusing ull = unsigned long long;\nusing ll = long long;\n\ninline int gcd(int a,int b) { if (b==0) return a; return gcd(b, a%b); }\ninline long long gcd(long long a,long long b) { if (b==0) return a; return gcd(b, a%b); }\ninline int lcm(int a,int b) { return a/gcd(a,b)*b; } \ninline long long lcm(long long a,long long b) { return a/gcd(a,b)*b; }\ninline long long nth_prime(long long a) { a++;if(a <= 6) return (vector<long long>{2,3,5,7,11,13,17})[a]; long double lg = log((long double) a); return (long long) floor(a * (lg + log(lg))); }\ninline long long mod_exp(long long base, long long exp, long long modd) { unsigned long long ans = 1; base %= modd; while(exp > 0) { if(exp%2==1) ans = (base*ans)%modd; exp /= 2; base = (base*base)%modd; } return ans; }\ninline string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>=\'a\' && a[i]<=\'z\') a[i]-=\'a\'-\'A\'; return a; }\ninline string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>=\'A\' && a[i]<=\'Z\') a[i]+=\'a\'-\'A\'; return a; }\n\n\nbool fIO() {\n    ios::sync_with_stdio(false);\n    ios_base::sync_with_stdio(false);\n    ios::sync_with_stdio(false);\n    cout.tie(nullptr);\n    cin.tie(nullptr);\n    return true;\n}\nbool y4555123 = fIO();\nconst ll MOD = 1e9 + 7;\nclass Solution {\npublic:\n    int countOfPairs(const vector<int>& nums) {\n        // This question is an optimization game, so every little optimization counts.\n        int n = (int) nums.size();\n        ll dp[1001][1001] {}; // dp[lastNumForIncreasing][lastNumForDecreasing]\n        for(ll i = 0; i <= nums[0]; i++) { // base case for 0\n            dp[i][nums[0]-i] = 1;\n        }\n        ll updates[1001] {};\n        // O(n) loop\n        for(int i = 1; i < n; i++) {\n            ll target = nums[i];\n            ll currWays = 0;\n            // Up to 1000\n            for(ll incr = 0; incr <= target; incr++) {\n                ll decr = target-incr;\n                currWays += dp[incr][decr];\n                ll compDecr = nums[i-1]-decr, compIncr = nums[i-1]-incr;\n                // compDecr is complement of decr to the previous num\n                // compIncr is complement of incr to the previous num\n                // The following adds up the valid subarrays\n                // for(ll j = 0; j < incr; j++) {\n                //     currWays += dp[j][decr];\n                //     currWays %= MOD;\n                // }\n                // for(ll j = decr+1; j <= 1000; j++) {\n                //     currWays += dp[incr][j];\n                //     currWays %= MOD;\n                // }\n                // We notice that the above loop is not needed, since the other index has to be the complement to nums[i-1] (previous num)\n                // So we can do the following and check if the bounds match\n                // This becomes O(1) instead of O(2*n)\n                if(compDecr >= 0 && compDecr < incr) {\n                    currWays += dp[compDecr][decr];\n                }\n                if(compIncr > decr && compIncr <= 1000) {\n                    currWays += dp[incr][compIncr];\n                }\n                currWays %= MOD; // Mod\n                // this is a slight optimization, using updates[1001] instead of newDp[1001][1001]\n                updates[incr] = currWays;\n            }\n            // Here, we clear everything in DP using the logic of complement to the previous number\n            // O(n) instead of O(n^2)\n            for(ll incr = 0; incr <= nums[i-1]; incr++) {\n                dp[incr][nums[i-1]-incr] = 0;\n            }\n            // Here we update the dp table that is now cleared with 0\'s\n            // This is O(n)\n            for(ll incr = 0; incr <= target; incr++) {\n                dp[incr][target-incr] = updates[incr];\n                updates[incr] = 0;\n            }\n        }\n        ll ans = 0;\n        // nums.back()-i is complement of i, so it is up to O(1000) not O(1000*1000)\n        for(ll i = 0; i <= nums.back(); i++) {\n            ans += dp[i][nums.back()-i];\n        }\n        return ans % MOD;\n    }\n};\n```\n## 1/3. Memoization\n```cpp\nclass Solution {\npublic:\n    int countOfPairs(const vector<int>& nums) {\n        int n = (int) nums.size();\n        vector<unordered_map<ll,ll>> memo(n, unordered_map<ll, ll>());\n        function<ll(int,ll,ll)> calc = [&](int len, ll prevIncreasing, ll prevDecreasing) -> ll {\n            if(len >= n) {\n                return 1;\n            }\n            if(auto itr = memo[len].find((prevIncreasing << 10) | prevDecreasing); itr != memo[len].end()) {\n                return itr->second;\n            }\n            int target = nums[len];\n            ll incr = prevIncreasing;\n            ll decr = (target - incr);\n            while(decr >= 0 && !(incr >= prevIncreasing && (prevDecreasing == -1 || decr <= prevDecreasing))) {\n                incr++;\n                decr--;\n            }\n            ll ways = 0;\n            while(decr >= 0 && incr >= prevIncreasing && (prevDecreasing == -1 || decr <= prevDecreasing)) {\n                ways += calc(len+1, incr, decr);\n                ways %= MOD;\n\n                incr++;\n                decr--;\n            }\n            return memo[len][(prevIncreasing << 10) | prevDecreasing] = ways;\n        };\n        return calc(0, 0, -1) % MOD;\n    }\n};\n```\n## 2/3. Slow Tabulation (433/801)\n```cpp\nclass Solution {\npublic:\n    int countOfPairs(const vector<int>& nums) {\n        int n = (int) nums.size();\n        ll dp[1001][1001] {}; // dp[lastNumForIncreasing][lastNumForDecreasing]\n        dp[0][nums.front()] = 1;\n        for(int i = 0; i < n; i++) {\n            ll target = nums[i];\n            ll currWays = 0;\n            ll newDp[1001][1001] {};\n            for(ll incr = 0; incr <= target; incr++) {\n                ll decr = target-incr;\n                currWays += dp[incr][decr];\n                for(ll j = 0; j < incr; j++) {\n                    currWays += dp[j][decr];\n                }\n                for(ll j = decr+1; j <= 1000; j++) {\n                    currWays += dp[incr][j];\n                }\n                \n\n                newDp[incr][decr] = currWays;\n            }\n            for(ll a = 0; a <= 1000; a++) {\n                for(ll b = 0; b <= 1000; b++) {\n                    dp[a][b] = newDp[a][b];\n                }\n            }\n        }\n        ll ans = 0;\n        for(ll i = 0; i < 1001; i++) {\n            for(ll j = 0; j < 1001; j++) {\n                ans += dp[i][j];\n                ans %= MOD;\n            }\n        }\n        return ans;\n    }\n};\n```\n## 3/3. Not as slow Tabulation (800/801)\n```cpp\nclass Solution {\npublic:\n    int countOfPairs(const vector<int>& nums) {\n        int n = (int) nums.size();\n        ll dp[1001][1001] {}; // dp[lastNumForIncreasing][lastNumForDecreasing]\n        for(ll i = 0; i <= nums[0]; i++) {\n            dp[i][nums[0]-i] = 1;\n        }\n        ll updates[1001] {};\n        for(int i = 1; i < n; i++) {\n            ll target = nums[i];\n            ll currWays = 0;\n            for(ll incr = 0; incr <= target; incr++) {\n                ll decr = target-incr;\n                currWays += dp[incr][decr];\n                ll compDecr = nums[i-1]-decr, compIncr = nums[i-1]-incr;\n                if(compIncr > decr && compIncr + incr == nums[i-1] && compIncr <= 1000) {\n                    currWays += dp[incr][compIncr];\n                }\n                if(compDecr >= 0 && compDecr + decr == nums[i-1] && compDecr < incr) {\n                    currWays += dp[compDecr][decr];\n                }\n\n                updates[incr] = currWays %= MOD;\n            }\n            for(ll incr = 0; incr <= nums[i-1]; incr++) {\n                dp[incr][nums[i-1]-incr] = 0;\n            }\n            for(ll incr = 0; incr <= target; incr++) {\n                dp[incr][target-incr] = updates[incr];\n                updates[incr] = 0;\n            }\n        }\n        ll ans = 0;\n        for(ll i = 0; i < 1001; i++) {\n            for(ll j = 0; j < 1001; j++) {\n                ans += dp[i][j];\n                ans %= MOD;\n            }\n        }\n        return ans;\n    }\n};\n```
['Array', 'Dynamic Programming', 'Memoization', 'C++']