107. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top-left to bottom-right that minimizes the sum of all numbers along its path. You can only move right or down.

Input: A 2D non-negative integer array grid of size m x n.

Output: Integer — minimum path sum from top-left to bottom-right.

Examples

Input: [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Path 1→3→1→1→1=7.

Input: [[1,2,3],[4,5,6]]
Output: 12
Explanation: Path 1→2→3→6=12.

Input: [[1]]
Output: 1
Explanation: Single cell.

Constraints

• m==grid.length
• n==grid[i].length
• 1<=m,n<=200
• 0<=grid[i][j]<=200

Asked by