Overview

Gems with certain values are placed on an \(N \times M\) grid, and you collect gems from the cells you pass through while moving from the top-left to the bottom-right, moving only right or down. The goal is to find the path that maximizes the total value of gems in the cells you pass through.

Analysis

In this problem, the number of “ways to choose a path” is extremely large, and brute-force search would lead to a combinatorial explosion, making it impractical. For example, when \(N = M = 1000\), the number of paths is \(_{1998}C_{999}\), which is an astronomically large number.

However, this can be solved efficiently using dynamic programming (DP), where we only consider “the maximum value upon reaching a given cell.”

Specifically, for each cell \((i, j)\), we sequentially compute the maximum total value among all paths that reach that cell. Since movement is restricted to “right” or “down” only, the cell visited immediately before cell \((i, j)\) is either \((i-1, j)\) or \((i, j-1)\). Therefore, we simply compare which of the two yields a greater value.

Algorithm

We use Dynamic Programming.

• Let dp[i][j] be “the maximum total value of gems along a path reaching cell \((i, j)\).”
• As the initial value, set dp[0][0] = A[0][0].
• For the leftmost column (\(i=0\)), movement is only possible from the left, so we compute it as a prefix sum: $\( dp[0][j] = dp[0][j-1] + A[0][j] \)$
• Similarly, for the top row (\(j=0\)): $\( dp[i][0] = dp[i-1][0] + A[i][0] \)$
• For all other cells, we choose the larger value between coming from above and coming from the left, then add the current cell’s value: $\( dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1]) + A[i][j] \)$

The final answer we want is dp[N-1][M-1].

Concrete Example

For example, given the following input:

3 3
1 2 3
4 5 6
7 8 9

The DP table becomes:

1	3	6
5	8	14
12	20	29

The maximum value is 29.

Complexity

• Time complexity: \(O(N \times M)\)
• Space complexity: \(O(N \times M)\)

Implementation Notes

• sys.stdin.read is used to read input efficiently.

• When initializing the DP table, the first row and column are handled specially using prefix sum computation.

• When updating each cell, be careful to select the maximum of the values from “above” and “left.”

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    A = []
    index = 2
    for i in range(N):
        row = list(map(int, data[index:index + M]))
        A.append(row)
        index += M
    
    # DPテーブル初期化
    dp = [[0] * M for _ in range(N)]
    dp[0][0] = A[0][0]
    
    # 初期条件：上端
    for j in range(1, M):
        dp[0][j] = dp[0][j - 1] + A[0][j]
    
    # 初期条件：左端
    for i in range(1, N):
        dp[i][0] = dp[i - 1][0] + A[i][0]
    
    # DP更新
    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 qwen3-coder-480b.