159. Minimum Path Sum

Medium · Dynamic Programming

You are given an m×n grid where each cell contains a non-negative number. Find the minimum sum of numbers along a path from the top-left corner to the bottom-right corner. You can only move right or down. The input is a 2D array (list of lists) representing the grid. Return a single integer: the minimum path sum.

Examples

Example 1
Input: [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Path 1→3→1→1→1 has sum 7
Example 2
Input: [[1,2,3],[4,5,6]]
Output: 12
Explanation: Path 1→2→3→6 has sum 12

Constraints