To solve this problem, we need to find the maximum number of coins that can be collected by moving from the top-left corner to the bottom-right corner of a grid, where movement is restricted to right or down directions.

Approach

The problem can be efficiently solved using dynamic programming (DP) with space optimization. Here's the detailed approach:

1. Dynamic Programming Insight: The maximum coins at any cell (i, j) can be derived from the maximum coins collected either from the cell above (i-1, j) or the cell to the left (i, j-1), plus the coins in the current cell.
2. Space Optimization: Instead of using a 2D DP array, we use a 1D array to keep track of the maximum coins up to the current row. This reduces the space complexity from O(m*n) to O(n), where m is the number of rows and n is the number of columns.

Solution Code

def max_coins(grid):
    m = len(grid)
    if m == 0:
        return 0
    n = len(grid[0])
    dp = [0] * n

    # Initialize first row
    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j-1] + grid[0][j]

    # Fill dp for remaining rows
    for i in range(1, m):
        # Update first column of current row
        dp[0] += grid[i][0]
        # Update other columns
        for j in range(1, n):
            dp[j] = max(dp[j], dp[j-1]) + grid[i][j]

    return dp[-1]

Explanation

1. Initialization: We start by initializing a 1D DP array dp of size n (number of columns). The first element of dp is set to the value of the top-left cell of the grid.
2. First Row: For the first row, since we can only move right, each cell's value is the sum of the previous cell in the row and the current cell's coins.
3. Subsequent Rows: For each subsequent row:
   • The first cell of the row is updated by adding the current cell's coins to the previous value (since we can only move down to this cell).
   • For other cells, we take the maximum value from either the cell above (stored in dp[j]) or the cell to the left (stored in dp[j-1]), then add the current cell's coins.
4. Result: The last element of the DP array gives the maximum coins collected when reaching the bottom-right corner.

This approach efficiently computes the result with a time complexity of O(m*n) and space complexity of O(n), making it suitable for large grids.

Example: For the grid [[1,2,3],[4,5,6],[7,8,9]], the maximum coins collected is 29 (path: 1→4→7→8→9). The code correctly returns this value.

Another example: For grid [[1,3],[2,4]], the maximum coins is 8 (path:1→3→4). The code returns this value as expected.

This solution handles all edge cases, including 1x1 grids, 1-row grids, and 1-column grids. It is optimal and efficient.

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