Minimum Path Sum

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 which minimizes the sum of all numbers along its path.

You can only move either down or right at any point in time. The problem can be solved using dynamic programming. The recurrence relation is given by:

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

where \(dp[i][j]\) represents the minimum path sum to reach cell \( (i,j) \) from the starting cell \( (0,0) \).

inputFormat

The first line contains two integers \(R\) and \(C\) representing the number of rows and columns in the grid respectively.

The next \(R\) lines each contain \(C\) non-negative integers separated by spaces, representing the grid.

outputFormat

Output a single integer which is the minimum path sum from the top-left to the bottom-right corner.

3 3
1 3 1
1 5 1
4 2 1

7