Python 2D DP Beats 100%
Complexity\n- Time complexity:\nO(Nmax(nums))\n\n- Space complexity:\nO(Nmax(nums))\n\n# Code\n\nclass Solution:\n    def countOfPairs(self, nums: List[int]) ->
# Complexity\n- Time complexity:\nO(N*max(nums))\n\n- Space complexity:\nO(N*max(nums))\n\n# Code\n```\nclass Solution:\n    def countOfPairs(self, nums: List[int]) -> int:\n\n        max_n = max(nums)\n        # Create a dp 2d array, \n        # with the rows representing the prev element in array1\n        # and the cols representing the position of the nums array\n        dp = [[0] * len(nums) for _ in range(max_n + 1)]\n\n        for i in range(len(nums) - 1, -1, -1):\n            for prev in range(max_n, -1, -1):\n\n                # We always sum the value from dp[prev+1][i], \n                # so we need to calculate later only the new possibilities by having the current prev instead of prev+1\n                val = dp[prev+1][i] if prev < max_n else 0\n\n                # We start from the last col, dp[prev][i] can\'t be bigger than prev\n                # And prev can\'t actually be the prev if it\'s bigger than nums[i-1]\n                # So if the prev is invalid here (prev > nums[i-1]) we assign 0\n                # If nums[i] < prev, we also assign 0 because there is no possible number to make arr1 motononic\n                # If not, there is one new possibility, we assign 1 + the possibilities from dp[prev+1][i]\n                if i == len(nums) - 1:\n                    if prev <= nums[i] and prev <= nums[i-1]:\n                        val += 1\n                elif i == 0:\n                    # For the first position, any number can be assigned here as there is no prev\n                    # So we always sum dp[prev][i+1], as this means how many possibilities dp[prev][i+1] have with the given prev only\n                    val += dp[prev][i+1]\n                else:\n\n                    # p1 is the prev for arr1\n                    p1 = prev\n                    # p2 is the complement of p1 to nums, so that p1 + p2 = nums[i-1]\n                    # p1/p2 = prev values, so we check nums[i-1] instead of nums[i]\n                    p2 = nums[i-1] - p1\n\n                    # if p2 is < 0, it\'s invalid, so we don\'t sum anything\n                    if p2 >= 0:\n                        # x = the min allowed value of column i given all the conditions\n                        # x must be greater or equals to p1\n                        # the complement to nums[i-1] (arr2[i-1] = nums[i-1] - p1) must be smaller or equals than p2, so arr2 is non-increasing\n                        # So we have x >= p1 and nums[i] - x <= p2, which solves to x >= max(p1, nums[i] - p2)\n                        x = max(p1, nums[i] - p2)\n                        # We then sum to val, how many possibilities i+1 have with x >= max(p1, nums[i] - p2)\n                        # As dp already keeps the cummulative values, dp[x][i+1] will have the sum for all possible values bigger or equals to x\n                        val += dp[x][i+1]\n\n                dp[prev][i] = val\n                    \n\n        # dp[0][0] will have the total accumulated possibilities\n        return dp[0][0] % (10**9+7)\n```
['Python3']