Description
Submission
typedef long long ll;
class Solution {
ll dp1[16][16]; // maximum path product
ll dp2[16][16]; // minimum path product
ll M = 1e9 + 7;
public:
int maxProductPath(vector<vector<int>>& grid) {
ll m = grid.size();
ll n = grid[0].size();
dp1[0][0] = dp2[0][0] = grid[0][0];
for(int i = 1; i < m; ++i) {
dp1[i][0] = dp1[i-1][0] * grid[i][0];
dp2[i][0] = dp2[i-1][0] * grid[i][0];
}
for(int i = 1; i < n; ++i) {
dp1[0][i] = dp1[0][i-1] * grid[0][i];
dp2[0][i] = dp2[0][i-1] * grid[0][i];
}
for(ll i = 1; i < m; ++i) {
for(ll j = 1; j < n; ++j) {
dp1[i][j] = max(max(dp1[i-1][j] * grid[i][j], dp2[i-1][j] * grid[i][j]),
max(dp1[i][j-1] * grid[i][j], dp2[i][j-1] * grid[i][j]));
dp2[i][j] = min(min(dp1[i-1][j] * grid[i][j], dp2[i-1][j] * grid[i][j]),
min(dp1[i][j-1] * grid[i][j], dp2[i][j-1] * grid[i][j]));
}
}
if(dp1[m-1][n-1] < 0) return -1;
return dp1[m-1][n-1]%M;
}
};