Minimum Path Sum in a Grid

You are given a grid of size m x n filled with non-negative integers. Your task is to find a path from the top-left corner to the bottom-right corner which minimizes the sum of all numbers along its path.

You can only move either down or right at any point in time.

The recurrence relation for the dynamic programming solution can be written as: \(dp[i][j] = \min(dp[i-1][j],\, dp[i][j-1]) + grid[i][j]\).

Input/Output via standard input and standard output.

inputFormat

The first line contains two integers m and n separated by a space, representing the number of rows and columns of the grid.

Each of the next m lines contains n integers separated by spaces, which represent the grid.

outputFormat

Output a single integer which is 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