Minimum Cost Path in a Grid

In this problem, you are given an (n \times n) grid of non-negative integers representing the cost at each cell. A robot starts at the top-left cell ((0,0)) and wants to reach the bottom-right cell ((n-1,n-1)). The robot can only move either right or down at any point in time. Your task is to calculate the minimum cost required for the robot to travel from the start to the destination.

Problem Details:

• You are allowed to move only to the right or downward.
• The cost of a path is the sum of the costs of the cells visited, including the start and finish cells.

The problem can be solved using dynamic programming. Let (dp[i][j]) be the minimum cost to reach cell ((i,j)) from the start. Then, the recurrence is given by:

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

with the proper initialization for the first row and first column.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) representing the size of the grid. Each of the following (n) lines contains (n) space-separated integers representing the cost values in the grid.

outputFormat

Output the minimum cost required to reach the bottom-right corner from the top-left corner. The result should be printed to standard output (stdout).## sample

3
1 3 1
1 5 1
4 2 1

7