[Dart] Prefix sum + DP + Simple Math
Intuition\nWe can use dynamic programming with prefix sum optimization to efficiently solve this by building up the count of valid pairs for each element in the
# Intuition\nWe can use dynamic programming with prefix sum optimization to efficiently solve this by building up the count of valid pairs for each element in the input array.\n\n# Approach\n1. Create a 2D DP table where:\n    - Rows represent the current index in the input array\n    - Columns represent possible values for arr1 at that index\n\n\n2. Initialize the first row of the DP table for the first element of the input array\n3. For each subsequent element in the input array:\n    - Iterate through possible values for arr1\n    - Calculate the corresponding value for arr2\n    - Check if the current pair satisfies the monotonic conditions with respect to the previous element\n    - If valid, get range count from the previous row by prefix sum trick\n    - Also add the count from the current row\'s previous column (if j > 0)\n\n4. The final result is the last non-zero count in the last row of the DP table\n## Key Optimization:\nWe use a prefix sum approach in the inner loop. Instead of iterating through all previous values each time, we calculate the maximum valid count (maximumCanCount) and use the DP value at that point. This effectively gives us the sum of all valid previous counts in constant time.\n# Complexity\n- Time complexity:\nO(N * M)\n\n- Space complexity:\nO(N * M)\n\n# Code\n```\nimport \'dart:math\';\nclass Solution {\n  final mod = 1000000007;\n  int countOfPairs(List<int> nums) {\n    // rows: current element of nums\n    // cols: possible elements of arr1 at the current point\n    final dp = List.generate(nums.length, (i) => List.filled(1001, 0));\n    dp[0][0] = 1;\n    for (int i = 1; i <= nums[0]; i++){\n      dp[0][i] = dp[0][i - 1] + 1;\n    }\n    for (int i = 1; i < dp.length; i++){\n      for (int j = 0; j <= nums[i]; j++){\n        final arr1 = j; // element of arr1\n        final arr2 = nums[i] - j; // element of arr2\n        if (arr2 > nums[i - 1]) continue; // no valid cases if arr2 element is greater than the previous num\n        // Possible range conditions:\n        // 1. prevArr1 <= arr1 (prevArr1 = prevArr1)\n        // 2. prevArr2 >= arr2 (prevArr2 = nums[i - 1] - prevArr1)\n        // Expanding condition 2: nums[i - 1] - prevArr1 >= arr2 \n        // Rearranging for prevArr1: prevArr1 <= nums[i - 1] - arr2\n        final maximumCanCount = min(arr1, nums[i - 1] - arr2);\n        dp[i][j] = (dp[i - 1][maximumCanCount] + (j > 0 ? dp[i][j - 1] : 0)) % mod;\n      }\n    }\n    // The last non-zero count in the final row is the largest count\n    int res = 0;\n    for (final a in dp.last){\n      if (a > 0) res = a;\n    }\n    return res;\n  }\n}\n```
['Math', 'Dynamic Programming', 'Prefix Sum', 'Dart']