Python实现多米诺纸牌（Domino Solitaire）：最大化得分技术问询

Great question! Let's break down how to solve this Domino Solitaire problem—where we need to maximize the total score from covering a 2-row grid with 2×1 dominoes—using an optimal dynamic programming (DP) approach, plus a clean Python implementation.

This problem has the classic hallmarks of a DP problem: overlapping subproblems and optimal substructure. Each choice we make for covering columns directly impacts the best possible score for the remaining grid, so DP is the perfect fit here.

State Definition #

Let’s define dp[i] as the maximum total score we can achieve by covering the first i columns of the grid.

Transition Logic #

We have two valid ways to cover up to the i-th column, and we’ll pick whichever gives a higher score:

1. Vertical domino in the i-th column: Place one domino covering both cells in the i-th column. The score added here is the absolute difference between the two values in the column. The transition is:
   dp[i] = dp[i-1] + abs(grid[0][i-1] - grid[1][i-1])
   (We use i-1 because Python uses 0-indexing for grid columns)

2. Horizontal dominoes across columns i-1 and i: Place two horizontal dominoes—one covering the top cells of columns i-1 and i, another covering the bottom cells of those columns. The score added here is the sum of the absolute differences of the top pair and bottom pair. The transition is:
   dp[i] = dp[i-2] + abs(grid[0][i-2] - grid[0][i-1]) + abs(grid[1][i-2] - grid[1][i-1])

For each i, we take the maximum of these two options to get the optimal score up to that column.

Base Cases #

• dp[0] = 0: No columns covered means a score of 0.
• dp[1] = abs(grid[0][0] - grid[1][0]): Only one column exists, so we have to place a vertical domino.

Here’s an efficient, easy-to-follow implementation that follows the logic above:

def max_domino_score(grid):
    # Get the number of columns (grid is guaranteed to have 2 rows)
    num_columns = len(grid[0])
    if num_columns == 0:
        return 0
    
    # Initialize DP array where dp[i] is max score for first i columns
    dp = [0] * (num_columns + 1)
    # Base case: first column
    dp[1] = abs(grid[0][0] - grid[1][0])
    
    for i in range(2, num_columns + 1):
        # Option 1: Add vertical domino in current column
        vertical_option = dp[i-1] + abs(grid[0][i-1] - grid[1][i-1])
        # Option 2: Add horizontal dominoes across previous and current column
        horizontal_option = dp[i-2] + abs(grid[0][i-2] - grid[0][i-1]) + abs(grid[1][i-2] - grid[1][i-1])
        # Take the maximum of the two valid options
        dp[i] = max(vertical_option, horizontal_option)
    
    return dp[num_columns]

# Example usage
if __name__ == "__main__":
    # Sample 2x4 grid
    sample_grid = [
        [1, 2, 10, 1],
        [10, 1, 2, 10]
    ]
    print("Maximum possible score:", max_domino_score(sample_grid))  # Output: 27

Let’s verify the sample calculation quickly:

• dp[1] = |1-10| = 9
• dp[2] = max(9 + |2-1|=10, 0 + |1-2| + |10-1|=1+9=10) → 10
• dp[3] = max(10 + |10-2|=18, 9 + |2-10| + |1-2|=9+8+1=18) → 18
• dp[4] = max(18 + |1-10|=27, 10 + |10-1| + |2-10|=10+9+8=27) → 27

内容的提问来源于stack exchange，提问作者Ritesh Jain