Natural sol if already solved 3250 using top-down dp( with detailed expl)
First get the bottom-up version\nAnalysis ur code in 3 aspects, and make changes (in part 1) if it will make the logic simpler. \n##### (1)state :\n    i, v : t
### First get the bottom-up version\nAnalysis ur code in 3 aspects, and make changes (in part 1) if it will make the logic simpler. \n##### **(1)state :**\n    i, v : tackle nums[0 \u2026 i], the last ele of arr1 = v,\n**then the last ele of arr2 = nums[i] - v;**\n\n##### **(2) r - r**\n    dp[i][v] = \u2211dp[i - 1][k], where k <= v \n(first get the rough fumula, the validation of such k implement later)\n##### (3) base case\n    dp[0][0\u2026nums[0]] = 1;\nreturn `\u2211dp[n - 1][0\u2026nums[n - 1]]`\n\nThen we try to write the `r-r` and see which part can be done using a more efficient way.\n\n```\nfor(i)// [1, n - 1]\n    for(j)//[0, nums[i]]\n        for(k) // [0, min(j, lastA1Max)](if lastA1Max isvalid)\n```\nthen we can see that using `prefix sum` can repalce `for(k)`, and only takes O(1) time. and we can update prefix sum in `for(j)`\n\n```\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, vector<int>(1001, 0));\n        vector<int>pfx(1001, 0);\n        for (int j = 0; j <= nums[0]; j++)\n        {\n            dp[0][j] = 1; \n            if(!j)pfx[j] = dp[0][j];\n            else\n                pfx[j] = (pfx[j - 1] + dp[0][j]) % MOD;\n        }\n        \n        for (int i = 1; i < n; i++) \n        {\n            vector<int>tmp(1001, 0);\n            for (int j = 0; j <= nums[i]; j++)\n            {\n                int a2 = nums[i] - j;\n                // Also lastA2Min = a2;\n                int lastA1Max = nums[i - 1] - a2;\n                // lastA1 <= lastA1Max\n                // lastA1 <= j\n                if(lastA1Max < 0 || (lastA1Max > nums[i - 1])) dp[i][j] = 0;\n                else\n                {\n                    lastA1Max = min(j, lastA1Max);\n                    dp[i][j] = pfx[lastA1Max];\n                }\n                if(!j)tmp[j] = dp[i][j];\n                else tmp[j] = (tmp[j - 1] + dp[i][j]) % MOD;\n            }\n            pfx = tmp;\n        }\n        int ans = 0;\n        for (int j = 0; j <= nums[n - 1]; j++) {\n            ans = (ans + dp[n - 1][j]) % MOD;\n        }\n        return ans;\n    }\n};\n\nauto init = []() {\n    ios_base::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return nullptr;\n}();\n```
['Dynamic Programming', 'Prefix Sum', 'C++']