Minimum Path Cost in a Grid

You are given a grid of integers with dimensions \(m \times n\). Each cell \(grid[i][j]\) represents the cost to step onto that cell. Starting from the top-left corner (cell \(1,1\)) you must reach the bottom-right corner (cell \(m,n\)). You are only allowed to move either right or down at any step.

Your task is to compute the minimum cost required to travel from the top-left to the bottom-right corner of the grid.

The optimal substructure can be defined using dynamic programming where the recurrence relation is given by:

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

with appropriate initialization along the top row and left column.

inputFormat

The first line of the input contains two space-separated integers \(m\) and \(n\), representing the number of rows and columns in the grid respectively. Each of the following \(m\) lines contains \(n\) space-separated integers representing the grid.

outputFormat

Output a single integer — the minimum path cost from the top-left corner to the bottom-right corner.

3 3
1 3 1
1 5 1
4 2 1

7