动态规划：硬币兑换变种问题的递归关系制表法实现求助

Let's work through fixing your tabulation code for this coin change variant where we count ways to make a sum using an even number of coins. First, let's recap what your recursive function does, then spot where your original tabulation went wrong, and build the correct dynamic programming solution step by step.

Recap of the Recursive Logic #

Your count_even function tracks two states for each subproblem:

• parity=False: We've used an even number of coins so far
• parity=True: We've used an odd number of coins so far
  For each coin, you have two choices:

1. Skip the current coin: keep the same parity and coin set size
2. Use the current coin: flip the parity (since we added one coin) and subtract the coin's value from the remaining sum

Why Your Original Tabulation Failed #

Your 3D array idea was correct in theory, but two key issues broke the implementation:

• Confusing state dimension order: The order of [parity][sum][coin index] made it hard to align with the recursive logic's flow, and your loop order didn't properly propagate state changes through each coin type.
• Misaligned transition logic: When choosing to use a coin, you need to reference the current coin set (not the previous one) for the flipped parity state—your code didn't handle this correctly.

Correct Tabulation Implementation (3D DP Array) #

Let's start with an explicit 3D DP array that directly maps to your recursive logic. We'll define dp[j][p][i] as:

• j: Number of coin types we're using (from 0 to m; j=0 means no coins, j=m means all coins)
• p: Parity state (0 = even coin count, 1 = odd coin count)
• i: Current sum we're trying to reach (from 0 to n)
  The value dp[j][p][i] is the number of ways to make sum i using j coin types with a coin count of parity p.

def count_even_tabulation(coins, m, n):
    # Handle edge cases upfront
    if m <= 0 or n < 0:
        return 0
    if n == 0:
        return 1  # 0 coins is even, so there's 1 valid way
    
    # Initialize 3D DP array: dp[num_coins_used][parity][current_sum]
    dp = [[[0] * (n + 1) for _ in range(2)] for __ in range(m + 1)]
    
    # Base case: 0 coins used, sum 0, even count (0 coins)
    dp[0][0][0] = 1
    
    for j in range(1, m + 1):
        current_coin = coins[j - 1]
        for parity in range(2):
            for current_sum in range(n + 1):
                # Option 1: Skip the current coin, use only the first j-1 coins
                skip = dp[j - 1][parity][current_sum]
                
                # Option 2: Use the current coin (if sum allows it)
                # Using this coin flips the parity, so we reference the 1-parity state for sum - current_coin
                use = 0
                if current_sum >= current_coin:
                    use = dp[j][1 - parity][current_sum - current_coin]
                
                # Combine both options to get the total ways
                dp[j][parity][current_sum] = skip + use
    
    # Return ways to make sum n with all m coins, even parity (0)
    return dp[m][0][n]

Space-Optimized Version (2D DP Array) #

We can optimize the 3D array down to a 2D array since we only ever need the previous coin set's state and the current coin's flipped parity state. This cuts down on memory usage:

def count_even_tabulation_optimized(coins, m, n):
    if m <= 0 or n < 0:
        return 0
    if n == 0:
        return 1
    
    # dp[parity][sum]: current state of ways to make sum with given parity
    dp_prev = [[0] * (n + 1) for _ in range(2)]
    dp_prev[0][0] = 1  # Base case: 0 sum, even count (0 coins)
    
    for coin in coins:
        # Start with the previous state (skip current coin)
        dp_curr = [row.copy() for row in dp_prev]
        for parity in range(2):
            # Iterate from coin value to n to avoid incorrect reuse of the same coin
            for current_sum in range(coin, n + 1):
                # Using the coin flips the parity, so add ways from the 1-parity state
                dp_curr[parity][current_sum] += dp_curr[1 - parity][current_sum - coin]
        dp_prev = dp_curr
    
    return dp_prev[0][n]

Example Test #

Let's test with coins=[1,2,3], n=6:

• Both implementations return 4, matching the recursive function's result. The valid even-count combinations are:
  1. Six 1s (6 coins)
  2. Two 3s (2 coins)
  3. Four coins: 1+1+1+3
  4. Four coins: 1+1+2+2

内容的提问来源于stack exchange，提问作者Octavio Castillo