Dynamic programming with 2d array (Python)
2d array Dynamic Programming\n\n## Problem Statement\n\nWe are given an array of positive integers nums of length n. The goal is to find the number of monotonic
# 2d array Dynamic Programming\n\n## Problem Statement\n\nWe are given an array of positive integers `nums` of length `n`. The goal is to find the number of monotonic pairs \\((arr1, arr2)\\) such that:\n\n- `arr1` is monotonically non-decreasing: `arr1[0] <=  arr1[1]  <=  ... <=  arr1[n-1]`.\n- `arr2` is monotonically non-increasing: `arr2[0] >= arr2[1] >= ... >= arr2[n-1]`.\n- For each index `i,  arr1[i] + arr2[i] = nums[i]`.\n\nThe solution must return the count of such pairs modulo `10^9 + 7`.\n\n## Code Explanation\n\nThe code uses dynamic programming to solve the problem. Here\'s a breakdown of each part of the code:\n\n```python\nclass Solution(object):\n    def countOfPairs(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: int\n        """\n        MOD = 10**9 + 7\n        n = len(nums)\n\n        # Create a 2D dp array with size (n) x (max(nums) + 1)\n        max_num = max(nums)\n        dp = [[0] * (max_num + 1) for _ in range(n)]\n\n        # Initialize dp[0][j]\n        for j in range(nums[0] + 1):\n            dp[0][j] = 1\n```\n\n- **Initialization**:\n  - `MOD` is set to `10^9 + 7`to handle large numbers and avoid overflow.\n  - `n` is the length of the input array `nums`.\n  - `max_num` is the maximum value in `nums`, used to determine the size of the DP table.\n  - `dp` is a 2D list where `dp[i][j]` represents the number of ways to form valid arrays up to index `i` with `arr1[i] = j`.\n  - The first row of the DP table is initialized such that `dp[0][j] = 1` for all \\(j\\) from `0` to `nums[0]`, indicating that there\'s one way to choose `arr1[0] = j` and `arr2[0] = nums[0] - j`.\n\n```python\n        # Fill the dp table\n        for i in range(1, n):\n            prefix_sum = 0\n            diff = nums[i] - nums[i-1]\n\n            for j in range(max_num + 1):\n                # We accumulate the prefix sum to use in the next row\n                if j <= nums[i] and j >= diff:\n                    prefix_sum += dp[i - 1][min(j - diff, j)]\n                    prefix_sum %= MOD\n                    dp[i][j] = prefix_sum\n```\n\n- **Filling the DP Table**:\n  - The `for` loop iterates over each element `i` from `1` to `n-1`.\n  - `prefix_sum` is used to accumulate the number of ways to form valid arrays up to the previous index.\n  - `diff` is calculated as `nums[i] - nums[i-1]` to ensure the monotonic property of `arr2` holds (explained later).\n  - The inner loop iterates over each possible value of `j`, representing `arr1[i]`.\n  - The condition `j >= diff` ensures that `arr1[i]` is at least as large as `arr1[i-1] + (nums[i] - nums[i-1])`. This is necessary to satisfy \\(arr2[i] \\geq arr2[i-1] \\)\n  - `prefix_sum` is updated by adding the number of ways to form valid arrays up to the previous index (`i-1`) where `arr1[i-1]` can be between `0` and `min(j - diff, j)`.\n  - The result is taken modulo `MOD` to avoid overflow.\n\n```python\n        # The result is the sum of the last row in dp\n        result = sum(dp[n - 1][j] for j in range(nums[n - 1] + 1)) % MOD\n        return result\n```\n\n- **Result Calculation**:\n  - The final result is the sum of all entries in the last row of the DP table, `dp[n-1][j]`, for all `j` from `0` to `nums[n-1]`.\n  - The sum is taken modulo `MOD` to get the final result.\n\n## Key Insights\n\n- The code ensures that `arr1` is monotonically non-decreasing by comparing the current value `j` with the allowed minimum based on the previous index (`i-1`).\n- By accumulating the prefix sum up to the minimum allowed value, the code efficiently counts all valid configurations.\n- The use of dynamic programming allows the solution to handle large inputs efficiently by breaking down the problem into smaller subproblems and building up the solution incrementally.\n\nThis solution ensures that all conditions for monotonicity and sum are met while efficiently counting the number of valid pairs.
['Python']