Editorial: LeetCode 1594 Maximum Non Negative Product in a Matrix
https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/ from Google
Since we can only move down or right, and we must find a path to bottom right corner, so for each position in the matrix, we’ll have only one solution regardless where we come from. This means we can have a cache to memorize the solution so that we don’t calculate it over and over again. Once we realize this, we just need to calculate the only two next solutions (down and right), then use that solution to derive the solution for the current position, then return back. The only caveat is that we need to calculate both minimum and maximum because the value in the matrix can be possitive or negative.
這題跟大多數matrix題一樣，每一個座標的解只會受到右跟下的解影響，而且無關之前怎麼來的，所以我們可以把每個座標的解cache起來，這樣就不用重複計算已計算過的解。另一個要注意的點是因為這題matrix裡的值可正可負，所以當我們要計算最大正值的解的時候，我們會需要右跟下subproblem的最大解跟最小解，這樣如果我們本身是負值，那subproblem的最小解跟我們乘起來才會是我們要的解。
1class Solution {
2public:
3 typedef long long ll;
4 int R, C;
5 int MOD = 1e9+7;
6 vector<vector<ll>> maxdp;
7 vector<vector<ll>> mindp;
8 pair<ll, ll> dfs(int x, int y, vector<vector<int>>& grid) {
9 if (x == R-1 and y == C-1) return {grid[x][y], grid[x][y]};
10 if (maxdp[x][y] != -1357246) return {maxdp[x][y], mindp[x][y]};
11 vector<pair<ll, ll>> cand;
12 if (x < R-1)
13 cand.push_back(dfs(x+1, y, grid));
14 if (y < C-1)
15 cand.push_back(dfs(x, y+1, grid));
16 ll MAX=LLONG_MIN, MIN=LLONG_MAX;
17 for (auto p : cand) {
18 MAX = max(MAX, grid[x][y]*p.first);
19 MAX = max(MAX, grid[x][y]*p.second);
20 MIN = min(MIN, grid[x][y]*p.first);
21 MIN = min(MIN, grid[x][y]*p.second);
22 }
23 maxdp[x][y] = MAX;
24 mindp[x][y] = MIN;
25 return {MAX, MIN};
26 }
27 int maxProductPath(vector<vector<int>>& grid) {
28 R = grid.size();
29 C = grid[0].size();
30 maxdp.resize(R, vector<ll>(C, -1357246));
31 mindp.resize(R, vector<ll>(C, -1357246));
32 auto p = dfs(0, 0, grid);
33 if (p.first < 0) return -1;
34 return p.first%MOD;
35 }
36};