797. Minimum Path Sum in Grid (Recursive + Memoization)

Given an m x n grid filled with non-negative integers, find a path from the top-left corner to the bottom-right corner which minimizes the sum of all numbers along the path. You can only move RIGHT or DOWN at each step. Return the minimum path sum. Input is a JSON 2D array. Implement with recursion + memoization.

Input: A JSON 2D integer array of non-negative values.

Output: Return an integer — the minimum path sum.

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: [[0]]
Output: 0
Explanation: Single cell with value 0.

Constraints

• 1 <= m, n <= 50
• 0 <= grid[i][j] <= 1000

Asked by