Minimum Path Sum in Grid

You are given an integer n that represents the size of a grid, and an n × n grid filled with positive integers. Starting from the top-left cell, your task is to find the minimum path sum to reach the bottom-right cell.

You can only move either right or down at any point in time. The sum of a path is defined as the sum of all the numbers along that path.

A typical dynamic programming formulation for this problem is given by the following recurrence relation:

\(dp(i,j) = grid(i,j) + \min\big(dp(i-1,j),\, dp(i,j-1)\big)\)

with the base cases:

• \(dp(0,0) = grid(0,0)\)
• \(dp(0,j) = dp(0,j-1) + grid(0,j)\) for \(j \ge 1\)
• \(dp(i,0) = dp(i-1,0) + grid(i,0)\) for \(i \ge 1\)

Your goal is to implement an algorithm that computes \(dp(n-1, n-1)\), the minimum path sum from the top-left to the bottom-right cell.

inputFormat

The first line contains a single integer n, representing the number of rows (and columns) in the grid. This is followed by n lines, each containing n positive integers separated by spaces, representing the grid.

outputFormat

Output a single integer, which is the minimum path sum from the top-left cell to the bottom-right cell.## sample

3
1 3 1
1 5 1
4 2 1

7