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动态规划的Codeclass Solution { public: const int mod 1e9 30 -23; int maxProductPath(vectorvectorint grid) { int m grid.size(), n grid[0].size(); long long a, k, z; vectorvectorpairlong long, long long dp(m1, vectorpairlong long, long long(n1, {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记忆化回溯Codeclass Solution { public: vectorvectorbool status; int dir[2][2] {{1,0},{0,1}}; vectorvectorint gridgrid; int m, n, m1, n1; long long mx -1; unordered_mapint, pairlong long, long long mem; pairlong 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; pairlong long, long long tmp; for(int i 0; i 2; i) { zx x dir[i][0]; zy y dir[i][1]; if(zxmzynstatus[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(vectorvectorint grid) { m grid.size(), n grid[0].size(); m1 m - 1; n1 n - 1; status.assign(m, vectorbool(n, false)); gridgrid std::move(grid); status[0][0] true; pairlong long, long long ret dfs(0, 0); if(ret.second 0) return -1; return ret.second % mod; } };直接回溯的Codeclass Solution { public: vectorvectorbool status; int dir[2][2] {{1,0},{0,1}}; vectorvectorint 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(zx0zy0zxmzynstatus[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(vectorvectorint grid) { m grid.size(), n grid[0].size(); m1 m - 1; n1 n - 1; status.assign(m, vectorbool(n, false)); gridgrid std::move(grid); status[0][0] true; dfs(0, 0, gridgrid[0][0]); if(mx 0) return -1; return mx % mod; } };