Minimum Path Sum in a Grid

You are given an \(n \times n\) grid, where each cell contains an integer representing the cost to step on that cell. Your task is to find the path from the top-left cell to the bottom-right cell with the minimum total cost. You can only move either down or right at any step.

The dynamic programming recurrence for this problem is given by:

\(dp[i][j] = \min(dp[i-1][j],\; dp[i][j-1]) + grid[i][j]\)

If the grid is empty (i.e. \(n=0\)), the output should be 0.

inputFormat

The input is given from standard input. The first line contains an integer \(n\) denoting the size of the grid. If \(n = 0\), the grid is empty. Otherwise, the next \(n\) lines each contain \(n\) space-separated integers representing the grid rows.

outputFormat

Output a single integer on standard output, which is the minimum cost to reach the bottom-right cell starting from the top-left cell.

3
1 3 1
1 5 1
4 2 1

7