Description
Given an n x n grid, pick up maximum cherries traveling from (0,0) to (n-1,n-1) and back. -1 cells are blocked. Return the result as an integer.
Examples
Input:
grid = [[0,1,-1],[1,0,-1],[1,1,1]]Output:
5Explanation:
Two paths from (0,0) to (2,2): path 1 collects 3 (down-down-right-right), path 2 collects 2 more. Total: 5.
Input:
grid = [[1]]Output:
1Explanation:
Single cell with 1 cherry. Collect it going there; return path has nothing left. Total: 1.
Input:
grid = [[1,1,0,0],[0,-1,1,0],[1,0,-1,1],[1,0,1,1]]Output:
8Explanation:
DP simulates two people walking simultaneously. Optimal paths collect 8 cherries total, avoiding -1 blocks.
Constraints
- •
n == grid.length == grid[i].length - •
1 ≤ n ≤ 50