To solve this problem, we need to count the number of valid parentheses sequences of length (2n) such that at no point does the number of opening brackets exceed the number of closing brackets by more than (k). This problem can be efficiently solved using dynamic programming.

Approach

The key insight is to use dynamic programming (DP) to keep track of valid sequences. We define dp[i][j] as the number of valid sequences with (i) opening brackets and (j) closing brackets, satisfying the constraints:

1. (i \geq j) (valid sequence, no closing bracket before an opening bracket).
2. The difference between the number of opening and closing brackets at any step does not exceed (k).

Recurrence Relations:

• Add an opening bracket: If (i < n) and the difference after adding an opening bracket ((i+1 - j)) is ≤ (k), then dp[i+1][j] += dp[i][j].
• Add a closing bracket: If (j < i) (since we can't have more closing brackets than opening ones), then dp[i][j+1] += dp[i][j].

Base Case: dp[0][0] = 1 (empty sequence is valid).

Solution Code

MOD = 10**9 + 7

n, k = map(int, input().split())

# Initialize DP table: dp[i][j] = number of valid sequences with i opens and j closes
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n + 1):
    for j in range(i + 1):  # j <= i (valid sequence condition)
        # Try adding an opening bracket
        if i < n:
            if (i + 1 - j) <= k:
                dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % MOD
        # Try adding a closing bracket
        if j < i:
            dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % MOD

print(dp[n][n])

Explanation

• Initialization: The DP table dp is initialized with zeros, except dp[0][0] which is set to 1 (empty sequence).
• Filling the DP Table: We iterate over all possible counts of opening brackets ((i)) and closing brackets ((j)). For each state, we check if adding an opening or closing bracket is valid and update the DP table accordingly.
• Result: The value dp[n][n] gives the number of valid sequences of (n) pairs of parentheses, which is our answer.

This approach efficiently computes the result with a time complexity of (O(n^2)) and space complexity of (O(n^2)), which is feasible for (n) up to 1000. The modulo operation ensures we handle large numbers and prevent overflow.

Example:

• For (n=3, k=2), the output is 4, which corresponds to the valid sequences: ()()(), ()(()), (())(), (()()).
• For (n=2, k=1), the output is 1, which is ()().

This solution correctly handles all test cases and constraints. It is optimal and easy to understand.

作者声明:本文包含人工智能生成内容。