leetcode 1594. 矩阵的最大非负积-耗时100-Maximum Non Negative Product in a Matrix
Problem: 1594. 矩阵的最大非负积-耗时100-Maximum Non Negative Product in a Matrix
耗时100%，三种方案的，1、直接回溯的，超时了；2、记忆化回溯深度优先搜索, 通过了；3、动态规划的呢
记忆化回溯，哈希表记录了当前单元格到右下角的最大值和最小值，最后返回最大值即可，只求正数最大值，所以最小值也需要考虑，因负数的最小值乘上一个负数可能变成最大值
动态规划的，dp[i][j]表示从(0, 0)到(i-1, j-1)的最大最小乘积，和记忆化回溯类似，考虑到负数，所以需要记录最小值，防止变成最大值，初始条件就是首行首列
递推公式就是 上侧，左侧和当前乘积的最大最小值
方案3动态规划的Code
class Solution { public: const int mod= 1e9 + 30 -23; int maxProductPath(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); long long a, k, z; vector<vector<pair<long long, long long>>> dp(m+1, vector<pair<long long, long long>>(n+1, {LLONG_MIN/100, LLONG_MAX/100})); dp[1][1] = {grid[0][0], grid[0][0]}; for(int i = 2; i <= m; i++) dp[i][1] = {dp[i-1][1].first * grid[i-1][0], dp[i-1][1].second * grid[i-1][0]}; for(int i = 2; i <= n; i++) dp[1][i] = {dp[1][i-1].first * grid[0][i-1], dp[1][i-1].second * grid[0][i-1]}; for(int i = 2; i <= m; i++) { for(int j = 1; j <= n; j++) { a = grid[i-1][j-1]; if(i-1 > 0) { dp[i][j].first = max({dp[i-1][j].first * a, dp[i-1][j].second * a}); dp[i][j].second = min({dp[i-1][j].first * a, dp[i-1][j].second * a}); } if(j-1 > 0) { dp[i][j].first = max({dp[i][j].first, dp[i][j-1].first * a, dp[i][j-1].second * a}); dp[i][j].second = min({dp[i][j].second, dp[i][j-1].first * a, dp[i][j-1].second * a}); } } } if(dp[m][n].first < 0) return -1; return dp[m][n].first % mod; } };方案2记忆化回溯Code
class Solution { public: vector<vector<bool>> status; int dir[2][2] = {{1,0},{0,1}}; vector<vector<int>> gridgrid; int m, n, m1, n1; long long mx = -1; unordered_map<int, pair<long long, long long>> mem; pair<long long, long long> dfs(int x, int y) { long long now = gridgrid[x][y], mi = LLONG_MAX, mx = LLONG_MIN; if(x == m1 && y == n1) { return {now, now}; } int key = x * n + y; if(mem.count(key) != 0) return mem[key]; int zx, zy; pair<long long, long long> tmp; for(int i = 0; i < 2; i++) { zx = x + dir[i][0]; zy = y + dir[i][1]; if(zx<m&&zy<n&&status[zx][zy]==false) { status[zx][zy] = true; tmp = dfs(zx, zy); mi = min({mi, tmp.first * now, tmp.second * now}); mx = max({mx, tmp.first * now, tmp.second * now}); status[zx][zy] = false; } } mem[key] = {mi, mx}; return {mi, mx}; } const int mod = 1e9 + 30 - 23; int maxProductPath(vector<vector<int>>& grid) { m = grid.size(), n = grid[0].size(); m1 = m - 1; n1 = n - 1; status.assign(m, vector<bool>(n, false)); gridgrid = std::move(grid); status[0][0] = true; pair<long long, long long> ret = dfs(0, 0); if(ret.second < 0) return -1; return ret.second % mod; } };直接回溯的Code
class Solution { public: vector<vector<bool>> status; int dir[2][2] = {{1,0},{0,1}}; vector<vector<int>> gridgrid; int m, n, m1, n1; long long mx = -1; void dfs(int x, int y, long long product) { if(x == m1 && y == n1) { mx = max(mx, product); return; } int zx, zy; for(int i = 0; i < 2; i++) { zx = x + dir[i][0]; zy = y + dir[i][1]; if(zx>=0&&zy>=0&&zx<m&&zy<n&&status[zx][zy]==false) { status[zx][zy] = true; dfs(zx, zy, product * gridgrid[zx][zy]); status[zx][zy] = false; } } } const int mod = 1e9 + 30 - 23; int maxProductPath(vector<vector<int>>& grid) { m = grid.size(), n = grid[0].size(); m1 = m - 1; n1 = n - 1; status.assign(m, vector<bool>(n, false)); gridgrid = std::move(grid); status[0][0] = true; dfs(0, 0, gridgrid[0][0]); if(mx < 0) return -1; return mx % mod; } };