Overview

This is a problem where you move from the top-left to the bottom-right of an \(N \times M\) grid, moving only right or down, while maximizing the total value of gems on the cells you pass through. It can be solved using typical 2-dimensional dynamic programming (DP).

Analysis

Key Observations

1. Movement Direction Restriction: Since you can only move right or down, to reach a cell \((i, j)\), you must come from either “the left cell \((i, j-1)\)” or “the upper cell \((i-1, j)\)”.

2. Optimal Substructure: To find the maximum value up to cell \((i, j)\), you simply choose the larger of the maximum value up to \((i-1, j)\) and the maximum value up to \((i, j-1)\), then add the value of the current cell.

Problems with the Naive Approach

Enumerating all paths causes the number of paths to grow exponentially. For example, when \(N = M = 1000\), the total number of paths becomes the astronomical number \(\binom{1998}{999}\), which is far too large to handle.

Solution

We use Dynamic Programming (DP). By calculating the maximum value to each cell only once and reusing those results, we can solve this efficiently.

Algorithm

Define \(dp[i][j]\) as “the maximum total gem value from start \((0, 0)\) to cell \((i, j)\)” (0-indexed).

Recurrence Relation: $\(dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + A[i][j]\)$

Initial Conditions and Boundaries: - \(dp[0][0] = A[0][0]\) (starting point) - First row: \(dp[0][j] = dp[0][j-1] + A[0][j]\) (can only come from the left) - First column: \(dp[i][0] = dp[i-1][0] + A[i][0]\) (can only come from above)

Concrete Example: Consider the following grid with \(N=2, M=3\).

1 3 1
1 5 1

DP table calculation process:

dp[0][0] = 1
dp[0][1] = 1 + 3 = 4
dp[0][2] = 4 + 1 = 5
dp[1][0] = 1 + 1 = 2
dp[1][1] = max(4, 2) + 5 = 9
dp[1][2] = max(5, 9) + 1 = 10

The answer is \(dp[1][2] = 10\).

Complexity

• Time Complexity: \(O(N \times M)\)
  • Because each cell is processed exactly once
• Space Complexity: \(O(N \times M)\)
  • Size of the DP table
  • Note: Can be reduced to \(O(M)\) by keeping only one row at a time

Implementation Notes

1. Index Handling: The problem statement uses 1-indexed, but the code is implemented with 0-indexed. Be careful not to get confused.

2. Boundary Condition Handling: The first row and first column can only be reached from the left and from above, respectively, so they are handled separately. This prevents out-of-bounds array access when referencing dp[i-1][j] or dp[i][j-1] for general cells.

3. Overflow Prevention: The maximum gem value is \(10^9\), and the maximum number of cells is \(10^6\), so the total value can reach approximately \(10^{15}\). In Python, you don’t need to worry about integer overflow, but in C++ and similar languages, you need to use long long.

Source Code

def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(N):
        row = list(map(int, input().split()))
        A.append(row)
    
    # dp[i][j] = maximum value from (1,1) to (i,j)
    dp = [[0] * M for _ in range(N)]
    
    # Initial value
    dp[0][0] = A[0][0]
    
    # Fill the first row (can only come from the left)
    for j in range(1, M):
        dp[0][j] = dp[0][j-1] + A[0][j]
    
    # Fill the first column (can only come from above)
    for i in range(1, N):
        dp[i][0] = dp[i-1][0] + A[i][0]
    
    # Fill the remaining cells
    for i in range(1, N):
        for j in range(1, M):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + A[i][j]
    
    print(dp[N-1][M-1])

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.