Maximum Sum Path in a Matrix

You are given a square matrix \(A\) of size \(n \times n\). Your task is to compute the maximum sum of values one can collect when moving from the top-left corner \(A_{1,1}\) to the bottom-right corner \(A_{n,n}\), with the constraint that you may only move either right or down at any step.

The problem can be formulated using dynamic programming. Define \(dp(i,j)\) as the maximum sum possible to reach cell \((i,j)\). The recurrence relation is given by:

[ dp(i,j) = \max{dp(i-1,j),\ dp(i,j-1)} + A_{i,j} ]

with the base condition \(dp(1,1) = A_{1,1}\). Your goal is to compute \(dp(n,n)\).

inputFormat

The first line of input contains a single integer \(n\) representing the dimensions of the square matrix. The following \(n\) lines each contain \(n\) space-separated integers representing the rows of the matrix.

outputFormat

Output a single integer representing the maximum sum path from the top-left corner to the bottom-right corner of the matrix.

3
1 2 3
4 5 6
7 8 9

29