基于动态规划求解合法字符串数量的算法设计需求

Problem Recap #

We need to count the number of valid strings of length n composed of {A,B,C} that satisfy:

• No 3 consecutive As
• At most 1 B in the entire string
• Confirmed result for n=4 is 43

State Definition (Formalized) #

Your initial state parameters are perfect—let's formalize them clearly:
dp[i][b_remaining][a_remaining] = number of valid strings of length i where:

• b_remaining: Number of Bs we can still use (0 or 1, since we're limited to 1 total)
• a_remaining: Number of consecutive As we can still add without hitting 3 in a row (0, 1, or 2). This translates to:
  • a_remaining = 2: Current string ends with a non-A (or is empty), so we can add up to 2 consecutive As
  • a_remaining = 1: Current string ends with 1 consecutive A, so we can add 1 more A
  • a_remaining = 0: Current string ends with 2 consecutive As, so we can't add any more As

Initialization #

Start with the empty string (length 0):
dp[0][1][2] = 1
This makes sense: we have 1 B left to use, and can add up to 2 consecutive As (since the string is empty).

State Transitions #

For each state (i, b, a), we can add A, B, or C (if allowed):

1. Add A: Only allowed if a_remaining > 0 (we haven't hit 2 consecutive As yet). Adding A reduces the consecutive A allowance by 1, and leaves the remaining B count unchanged:
   dp[i+1][b][a-1] += dp[i][b][a] (when a > 0)
2. Add B: Only allowed if b_remaining > 0 (we haven't used our single B yet). Adding B resets the consecutive A allowance to 2 (since we've broken any A streak), and reduces the remaining B count to 0:
   dp[i+1][b-1][2] += dp[i][b][a] (when b > 0)
3. Add C: Allowed in any state. Adding C resets the consecutive A allowance to 2 (breaks any A streak), and leaves the remaining B count unchanged:
   dp[i+1][b][2] += dp[i][b][a] (for all valid b and a)

Final Result Calculation #

The total number of valid strings of length n is the sum of all possible states at i=n:
total = sum(dp[n][b][a] for b in 0,1 for a in 0,1,2)

Space Optimization #

Since we only need the previous length's state to compute the next, we don't need to store the entire n x 2 x 3 array. We can use two 2x3 arrays: current (for length i) and next (for length i+1). This reduces space complexity to O(1) (constant space), while keeping time complexity at O(n).

Pseudocode #

def count_valid_strings(n):
    # Initialize current state: length 0, 1 B remaining, 2 consecutive As allowed
    current = [[0]*3 for _ in range(2)]
    current[1][2] = 1  # current[b_remaining][a_remaining]

    for _ in range(n):
        next_state = [[0]*3 for _ in range(2)]
        for b in [0, 1]:
            for a in [0, 1, 2]:
                count = current[b][a]
                if count == 0:
                    continue
                # Add A
                if a > 0:
                    next_state[b][a-1] += count
                # Add B
                if b > 0:
                    next_state[b-1][2] += count
                # Add C
                next_state[b][2] += count
        current = next_state

    # Sum all valid states for length n
    total = 0
    for b in [0, 1]:
        total += sum(current[b])
    return total

Verification with n=4 #

Running the pseudocode for n=4 returns 43, which matches the given result. We can manually walk through the transitions to confirm each step's validity—every state update aligns with the problem constraints.

Key Notes #

• Time complexity: O(n) — we loop n times, and each iteration processes 6 states (2*3)
• Space complexity: O(1) — we only keep track of two small arrays
• The state definitions directly map to your initial parameters, making the logic intuitive and easy to maintain

内容的提问来源于stack exchange，提问作者Sheraz Faraj