Minimum Path Sum in a Grid

You are given a 2D grid of non-negative integers. Your task is to find a path from the top-left corner to the bottom-right corner of the grid such that the sum of the numbers along the path is minimized. At any point, you may only move either right or down.

The optimal substructure of the problem can be formulated as follows:

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

with the appropriate initialization for the first row and first column. This recurrence relation ensures that you always accumulate the minimum sum possible while moving only right or down.

inputFormat

The first line of the input contains two integers m and n representing the number of rows and columns of the grid. Each of the next m lines contains n space-separated non-negative integers, representing the grid values.

outputFormat

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

Recall the recurrence:

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

3 3
1 3 1
1 5 1
4 2 1

7