1import java.util.Arrays;
2
3class Solution {
4  
5    public int countOfPairs(int[] nums) {
6        final int MOD = (int) 1e9 + 7; // Define the modulo constant for large numbers
7        int n = nums.length; // Length of the input array
8        int maxNum = Arrays.stream(nums).max().getAsInt(); // Find the maximum number in the array
9
10        int[][] dp = new int[n][maxNum + 1]; // Initialize DP array
11        // Initialize the first row of DP table
12        for (int j = 0; j <= nums[0]; ++j) {
13            dp[0][j] = 1;
14        }
15      
16        int[] prefixSum = new int[maxNum + 1]; // Array to store prefix sums for optimization
17      
18        // Fill the DP table
19        for (int i = 1; i < n; ++i) {
20            // Compute prefix sums based on the previous row
21            prefixSum[0] = dp[i - 1][0];
22            for (int j = 1; j <= maxNum; ++j) {
23                prefixSum[j] = (prefixSum[j - 1] + dp[i - 1][j]) % MOD;
24            }
25          
26            // Calculate the DP for current row
27            for (int j = 0; j <= nums[i]; ++j) {
28                int k = Math.min(j, j + nums[i - 1] - nums[i]);
29                if (k >= 0) {
30                    dp[i][j] = prefixSum[k];
31                }
32            }
33        }
34      
35        // Calculate the final answer by summing up the last row of the DP table
36        int result = 0;
37        for (int j = 0; j <= nums[n - 1]; ++j) {
38            result = (result + dp[n - 1][j]) % MOD;
39        }
40        return result;
41    }
42}
43

1class Solution {
2public:
3    int countOfPairs(vector<int>& nums) {
4        const int mod = 1e9 + 7;  // Define the modulus value for result to prevent overflow
5        int n = nums.size();  // Calculate the size of the input vector 'nums'
6        int maxNum = *max_element(nums.begin(), nums.end());  // Find the maximum element in 'nums'
7      
8        // Create a 2D vector 'f' for dynamic programming, initialized with zeros
9        vector<vector<int>> f(n, vector<int>(maxNum + 1, 0));
10      
11        // Initialize the first row with 1 up to nums[0] since the first number can form pairs with itself
12        for (int j = 0; j <= nums[0]; ++j) {
13            f[0][j] = 1;
14        }
15      
16        // Create a vector 'g' to hold cumulative sums of the previous row for optimized calculations
17        vector<int> g(maxNum + 1, 0);
18      
19        // Fill the DP table using previously computed results
20        for (int i = 1; i < n; ++i) {
21            g[0] = f[i - 1][0];  // Initialize the first value of g with the previous row's first element
22
23            // Fill 'g' with cumulative sum of the previous row, modulated
24            for (int j = 1; j <= maxNum; ++j) {
25                g[j] = (g[j - 1] + f[i - 1][j]) % mod;
26            }
27
28            // Calculate the DP results for the current row
29            for (int j = 0; j <= nums[i]; ++j) {
30                int k = min(j, j + nums[i - 1] - nums[i]);  // Determine the farthest index in the previous row to consider
31
32                if (k >= 0) {
33                    f[i][j] = g[k];  // Assign the cumulative sum up to 'k' to the current position
34                }
35            }
36        }
37
38        int result = 0;  // Initialize the result to accumulate the final number of pairs
39
40        // Sum all possible pair counts from the last DP row to get the final answer
41        for (int j = 0; j <= nums[n - 1]; ++j) {
42            result = (result + f[n - 1][j]) % mod;
43        }
44      
45        return result;  // Return the total count of valid pairs
46    }
47};
48

1function countOfPairs(nums: number[]): number {
2    const mod = 1e9 + 7; // Modulo value for large number computations to avoid overflow
3    const n = nums.length; // Length of the input array
4    const m = Math.max(...nums); // Maximum value in the input array
5  
6    // Initialize a 2D array `f` to hold the count of pairs
7    // `f[i][j]` represents the number of valid ways to achieve a sum 'j' using the first 'i' numbers
8    const f: number[][] = Array.from({ length: n }, () => Array(m + 1).fill(0));
9  
10    // Base case: with the first number, we can only achieve sums from 0 to nums[0]
11    for (let j = 0; j <= nums[0]; j++) {
12        f[0][j] = 1;
13    }
14
15    // Temporary array `g` to manipulate rolling sums efficiently for dynamic programming
16    const g: number[] = Array(m + 1).fill(0);
17  
18    // Iterate through each number from the second one to the last
19    for (let i = 1; i < n; i++) {
20        // Initialize the rolling sum array `g`
21        g[0] = f[i - 1][0];
22      
23        // Populate `g` with cumulative sums to facilitate quick access
24        for (let j = 1; j <= m; j++) {
25            g[j] = (g[j - 1] + f[i - 1][j]) % mod;
26        }
27      
28        // Update `f[i][j]` based on the previous results and the rules given
29        for (let j = 0; j <= nums[i]; j++) {
30            const k = Math.min(j, j + nums[i - 1] - nums[i]); // Calculate the valid boundary based on current and previous values
31            if (k >= 0) {
32                // If valid, then count the sums that can form `j` using the available previous results
33                f[i][j] = g[k];
34            }
35        }
36    }
37  
38    let ans = 0; // To store the final answer
39    // Sum up all counts for the last number in `nums` to get the total number of valid pairs
40    for (let j = 0; j <= nums[n - 1]; j++) {
41        ans = (ans + f[n - 1][j]) % mod;
42    }
43  
44    return ans; // Return the total count of pairs modulo `mod`
45}
46