Dynamic Programming Beats 100% - Counting Monotonic Pairs in Arrays
\n\n### Problem Statement\nGiven an array $nums$ of positive integers, we want to count the number of possible pairs of two arrays $arr1$ and $arr2$ of non-nega
![Screenshot 2024-08-11 at 15.13.02.png](https://assets.leetcode.com/users/images/d83b5d36-6cc9-42e4-b915-f8689bdf8c5b_1723364016.9072099.png)\n\n### Problem Statement\nGiven an array $nums$ of positive integers, we want to count the number of possible pairs of two arrays $arr1$ and $arr2$ of non-negative integers such that:\n\n0. $0 \\leq nums[i] \\leq 1000$\n1. $arr1$ is a non-decreasing array.\n2. $arr2$ is a non-increasing array.\n3. The sum of corresponding elements in $arr1$ and $arr2$ equals the corresponding element in $nums$, i.e., $arr1[i] + arr2[i] == nums[i]$.\n\n### Intuition\nThe problem is asking us to form pairs of arrays $arr1$ and $arr2$ under the constraints provided. A brute-force approach would involve checking all possible pairs, but this would be inefficient due to the exponential number of possible combinations.\n\nInstead, we can use dynamic programming (DP) to solve the problem efficiently. The idea is to build solutions for smaller subproblems and combine them to solve the larger problem.\n\n### Dynamic Programming Approach\nLet\'s define a DP table $f[i][x] (0 \\leq i \\leq n - 1, 0 \\leq x \\leq 1000$:\n\n- $f[i][x]$ represents the number of valid monotonic pairs of length $i+1$ where the last element of $arr1$ is $x$ and the last element of $arr2$ is $nums[i] - x$.\n\nGiven the above definition, we can break down the problem recursively:\n\n1. **Base Case**: \n   - For the first element $nums[0]$, any pair $(arr1[0], arr2[0])$ where $arr1[0] = x$ and $arr2[0] = nums[0] - x$ is valid. Therefore, we initialize:\n     $$\n     f[0][x] = 1 \\quad \\text{for all } x \\in [0, nums[0]]\n     $$\n\n2. **Recurrence Relation**:\n   - To fill $f[i][x]$, we need to sum all possible valid pairs from the previous index $i-1$. This can be expressed as:\n     $$\n     f[i][x] = \\sum_{prevX=0}^{\\min(x, x - nums[i] + nums[i-1])} f[i-1][prevX] \\quad (1)\n     $$\n   - Here, $prevX$ must satisfy:\n     - $prevX \\leq x$, ensuring $arr1$ is non-decreasing.\n     - $nums[i-1] - prevX \\geq nums[i] - x \\iff preV \\leq x - nums[i] + nums[i - 1]$, ensuring $arr2$ is non-increasing.\n     - => $prevX \\leq min(x, x - nums[i] + nums[i - 1])$\n\n3. **Optimizing with Prefix Sums**:\n   - To efficiently calculate the sum, for each iteration $i$ when we build $f[i][..]$, we can use a prefix sum array:\n     $$\n     \\text{prefixSum}[y] = \\sum_{j=0}^{y} f[i-1][j]\n     $$\n   - With this, the recurrence $(1)$ becomes:\n     $$\n     f[i][x] = \\text{prefixSum}[\\min(x, x - nums[i] + nums[i-1])]\n     $$\n    + Remember if $x - nums[i] + nums[i-1] < 0$, we can ignore this calculation because the index would be invalid (negative)\n\n4. **Final Calculation**:\n   - After filling the DP table, the result is the sum of all valid pairs at the last index $n-1$:\n     $$\n     \\text{result} = \\sum_{x=0}^{nums[n - 1]} f[n-1][x]\n     $$\n\n# Complexity\n- Time complexity: $O(n * 1000)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: $O(n * 1000)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Reference Implementation in Rust:\n```rust\nimpl Solution {\n  pub fn count_of_pairs(nums: Vec<i32>) -> i32 {\n    let MOD = 1_000_000_007;\n\n    let n = nums.len();\n    let mut countMonotonicPairs = vec![vec![0; 1001]; n];\n\n    // calculate countMonotonicPairs[0][x] for x in 0..=1000\n    for x in 0..=nums[0] {\n      countMonotonicPairs[0][x as usize] = 1;\n    }\n\n    for i in 1..=n - 1 {\n      let mut prefixSum = vec![0; 1001];\n      for x in 0..=1000 {\n        if x > 0 {\n          prefixSum[x] = prefixSum[x - 1] + countMonotonicPairs[i - 1][x];\n        } else {\n          prefixSum[x] = countMonotonicPairs[i - 1][x];\n        }\n        prefixSum[x] %= MOD;\n      }\n      for x in 0..=nums[i] {\n        let left = x;\n        let right = x - nums[i] + nums[i - 1];\n        let threshold = if left < right { left } else { right };\n        if threshold >= 0 {\n          countMonotonicPairs[i][x as usize] = prefixSum[threshold as usize];\n        }\n      }\n    }\n\n    let mut res = 0;\n    for x in 0..=nums[n - 1] {\n      res += countMonotonicPairs[n - 1][x as usize];\n      res %= MOD;\n    }\n\n    return res;\n  }\n}\n```\n\n# Follow-up\nHow can we optimize this even further? Can we optimize the recurrence formula or derive a lightweight math formula? Let\'s think about that.\n\n### Conclusion\nThis solution efficiently computes the number of valid monotonic pairs by using dynamic programming with prefix sums. Good luck and get AC.\n
['Dynamic Programming', 'Rust']