Minimum Path Sum

Imagine you're navigating a grid of numbers, and your goal is to find the path from the top-left corner to the bottom-right corner that has the smallest possible sum. This is a fundamental problem in pathfinding and optimization, with applications in areas like robotics, network routing, and game AI where efficient traversal is key.

Problem Description

You are given a 2D grid, grid, filled with non-negative integers. You need to find a path from the top-left cell (index (0, 0)) to the bottom-right cell (index (rows-1, cols-1)) such that the sum of all numbers along the path is minimized.

Key Requirements:

• You can only move either down or right at any point in time.
• The path must start at grid[0][0] and end at grid[rows-1][cols-1].

Expected Behavior: Your function should return a single integer representing the minimum sum of a valid path.

Edge Cases:

• A grid with only one row or one column.
• A grid with a single cell.

Examples

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: The path 1 → 3 → 1 → 1 → 1 has the minimum sum of 7.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Explanation: The path 1 → 2 → 3 → 6 has the minimum sum of 12.

Example 3:

Input: grid = [[5]]
Output: 5
Explanation: The grid has only one cell, so the path is just that cell.

Constraints

• 1 <= grid.length, grid[0].length <= 200 (The grid will have at least one row and one column, and at most 200 rows and 200 columns.)
• 0 <= grid[i][j] <= 100 (All numbers in the grid are non-negative and do not exceed 100.)

Notes

Consider how the cost to reach a particular cell is related to the costs of reaching the cells from which you could have arrived. This problem can be efficiently solved using dynamic programming.