To solve this problem, we need to find the maximum sum of a path from the top-left corner to the bottom-right corner of a 2D matrix, where movement is restricted to right or down directions. This is a classic dynamic programming problem that can be optimized for space efficiency.

Approach

The key insight is to use dynamic programming (DP) to keep track of the maximum sum to reach each cell. Here's the detailed approach:

1. Base Cases:

   • The starting cell (0,0) has a sum equal to its value.
   • For the first row (only right moves allowed), the sum to each cell is the sum of the previous cell in the row plus the current cell value.
   • For the first column (only down moves allowed), the sum to each cell is the sum of the previous cell in the column plus the current cell value.

2. General Case:

   • For any other cell (i,j), the maximum sum to reach it is the maximum of the sum from the cell above (i-1,j) or the cell to the left (i,j-1) plus the current cell value.

3. Space Optimization:

   • Instead of using a 2D DP matrix, we can use a 1D array. This is because to compute the sum for the current row, we only need the previous row's values (stored in the 1D array) and the current row's previous values (also in the same array).

Solution Code

def max_path_sum(matrix):
    if not matrix or not matrix[0]:
        return 0

    m = len(matrix)
    n = len(matrix[0])
    dp = [0] * n

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

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

    return dp[-1]

Explanation

• Initialization: We start by initializing a 1D array dp to store the maximum sum up to each cell in the current row.
• First Row: The first row is filled by accumulating the sum from the left (since we can only move right).
• Subsequent Rows: For each row, we first update the first element (since we can only come from above). Then, for each cell in the row, we take the maximum of the value from the cell above (stored in dp[j]) or the cell to the left (stored in dp[j-1]) and add the current cell value.
• Result: The last element of the dp array gives the maximum sum path to the bottom-right corner.

This approach efficiently computes the result with a time complexity of O(mn) (where m and n are the dimensions of the matrix) and a space complexity of O(n) (optimized from O(mn) using a 1D array). This makes it suitable for large matrices.

Example: For the matrix [[1,3,1],[1,5,1],[4,2,1]], the maximum path sum is 12 (path: 1→3→5→2→1). The code correctly returns this value.

Edge Cases: Handles 1x1 matrices (returns the only element), 1xN matrices (sum of all elements), and Nx1 matrices (sum of all elements).

This solution is optimal and easy to understand, making it a great choice for solving this problem.

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