Minimum Path Sum

Given a 2D grid of non-negative integers, find a path from the top-left corner to the bottom-right corner such that the sum of the numbers along the path is minimized. You can only move either down or right at any point in time.

Problem details: If we denote the grid as \(grid\) of size \(m \times n\), then you are to compute the minimal path sum by defining a state \(dp[i,j]\) which represents the minimum sum to reach cell \((i, j)\). The recurrence relation used is:

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

with the appropriate initialization at \(dp[0,0] = grid[0,0]\) and proper handling of the first row and first column. The final answer is \(dp[m-1,n-1]\).

inputFormat

The input is given via standard input. The first line contains two integers \(m\) and \(n\) denoting the number of rows and columns respectively. The following \(m\) lines each contain \(n\) space-separated integers representing the grid.

outputFormat

Output a single integer to standard output – the minimum path sum from the top-left corner to the bottom-right corner of the grid.

3 3
1 3 1
1 5 1
4 2 1

7