Given a 2D grid of non-negative integers grid with m rows and n columns, and a list of query cells queries, return the minimum path sum from the top-left cell (0, 0) to each queried cell. A path may move only right or down. The goal is to optimize performance when many queries are asked on the same grid.
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]], queries = [[2,2],[1,2]]
Output: [7, 6]
Explanation: The minimum path sums to (2,2) and (1,2) are 7 and 6.
Example 2:
Input: grid = [[5,1],[2,1]], queries = [[0,1],[1,1],[1,0]]
Output: [6, 7, 7]
Explanation: Precomputing all reachable minimum sums lets each query be answered in constant time.
1 <= m, n <= 5000 <= grid[r][c] <= 10^41 <= queries.length <= 10^50 <= queries[i][0] < m0 <= queries[i][1] < ngrid = [[1,3,1],[1,5,1],[4,2,1]], queries = [[2,2],[1,2]]Output[7, 6]WhyThe cheapest path to (2,2) has sum 7, and the cheapest path to (1,2) has sum 6.grid = [[5,1],[2,1]], queries = [[0,1],[1,1],[1,0]]Output[6, 7, 7]WhyAfter one DP pass over the grid, each queried cell is answered directly from the precomputed table.1 <= m, n <= 5000 <= grid[r][c] <= 10^41 <= queries.length <= 10^50 <= queries[i][0] < m0 <= queries[i][1] < ndef min_path_sum_queries(grid, queries):