Steps by steps, from problem I to problem II, O(n*m^2) -> O(n*m)
Intuition\n Describe your first thoughts on how to solve this problem. \n1. problem I: You see that it has to cnt # of ways & the condition is to based on previ
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. problem I: You see that it has to cnt # of ways & the condition is to based on previous situation. So, it must be "DP" problem. \n2. Problem II: After you finish the problem I, how can you simplify your calculation after rearrange your formula?\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst bear in mind there are 3 conditions:\n- arr1[0] <= arr1[1] <= ... <= arr1[n - 1]\n- arr2[0] >= arr2[1] >= ... >= arr2[n - 1]\n- arr1[i] + arr2[i] == nums[i]\n\nThen, now we can think the solution\n1. there are n grid (n <= 2000), for each grid it can have m cases(m = 50 in problem I), that is, you can fill i-th grid for arr1 with 0 to nums[i] (condition 3). Thus, your dp table would be n x m, first for the position i and second for the number j you want to fill in that grid of arr1. Now think of what you should consider for each entry (i, j) in the table? If you give arr1[i] = j and give arr2[i] = nums[i] - j, then arr1[i-1] <= j (condition 1) and arr2[i-1] = nums[i-1] - arr1[i-1] >= nums[i] - j. So we must consider different value of arr[i-1] as k. Now you can go for the code.\n2. we know for j \n`code`     k <= j && nums[i - 1] - k >= nums[i] - j (problem I)\n `code`    k < = min(j, j -(nums[i] - nums[i-1]))  (rearrange)\nfor j + 1, the k we should consider is\n`code` k\' < = min(j+1, j+1 -(nums[i] - nums[i-1]))  \nYou\'ll find that there is at most one more grid you have to consider from j to j + 1. So you can simplify the loop for k\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1. O(n*m^2) for problem I\n2. O(n*m) for problem II\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int MOD = 1e9 + 7;\n\n    int countOfPairs(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> arr1(n);\n        vector<int> arr2(n);\n        vector<vector<int>> dp(n, vector<int>(1001, 0));\n        for (int j = 0; j <= nums[0]; j++)\n            dp[0][j] = 1;\n        for (int i = 1; i < n; i++){\n            int ways = 0;\n            int k = 0;\n            for (int j = 0; j <= nums[i]; j++){\n                // problem I\n                // for (int j = 0; j <= nums[i]; j++){\n                //     int ways = 0;\n                //     for (int k = 0; k <= 50; k++){\n                //         if (k <= j && nums[i - 1] - k >= nums[i] - j)\n                //             ways = (ways + dp[i - 1][k]) % MOD;\n                //     }\n                //     dp[i][j] = ways;\n                // }\n                // problem II\n                if (k <= min(j, j - (nums[i] - nums[i - 1]))){\n                    ways = (ways + dp[i - 1][k]) % MOD;\n                    k++;\n                }\n                dp[i][j] = ways;\n            }\n        }\n        int res = 0;\n        for (int i = 0; i <= 1000; i++)\n            res = (res + dp[n - 1][i]) % MOD;\n        return res;\n    }\n};\n```
['C++']