本文涉及知识点

下载及打开打包代码的方法兼述单元测试
C++动态规划

LeetCode1594. 矩阵的最大非负积

给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。
在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。
返回 最大非负积 对 10⁹ + 7 取余 的结果。如果最大积为 负数 ，则返回 -1 。
注意，取余是在得到最大积之后执行的。
示例 1：

输入：grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1 。
示例 2：

输入：grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
输出：8
解释：最大非负积对应的路径如图所示 (1 * 1 * -2 * -4 * 1 = 8)
示例 3：

输入：grid = [[1,3],[0,-4]]
输出：0
解释：最大非负积对应的路径如图所示 (1 * 0 * -4 = 0)

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 15
-4 <= grid[i][j] <= 4

动态规划

动态规划

动态规划的状态表示

如果存在路径，则结果可能为正数，可能为0 。grid只要包括一个0，则经过此单格的路径积一定为0。下面只讨论为积为正数的情况。
long long型 dp[r][c][0] 表示到达(r,c)积为正数的最大绝对值，dp[r][c][1] 表示到达(r,c)积为负数的最大绝对值。空间复杂度：O(mn)。

动态规划的转移方程

(r1,c1)是前置单格,(r,c)后续单格。
v a l u e = { d p [ r 1 ] [ r 1 ] [ 0 ] × g r i d [ r ] [ c ] − d p [ r 1 ] [ r 1 ] [ 1 ] × g r i d [ r ] [ c ] value= \begin{cases} dp[r1][r1][0] \times grid[r][c] \\ -dp[r1][r1][1] \times grid[r][c] \\ \end{cases} value={dp[r1][r1][0]×grid[r][c]−dp[r1][r1][1]×grid[r][c]​
value = gird[r][c]。

auto Add = [&](int r, int c, long long value) {
					if (value < 0) {
						dp[r][c][1] = max(dp[r][c][1], -value);
					}
					else {
						dp[r][c][0] = max(dp[r][c][0], value);
					}
				};

单个状态转移的时间复杂度：O(1)，总时间复杂度：O(mn)

动态规划的初始化

如果grid[0][0]为非负，dp[0][0][0] =grid[0][0] ,否则dp[0][0][1] = abs(grid[0][0]);其它全为-1。

动态规划的返回值

dp.back().back()[0] % (1e9+7)
如果为-1，还需要判断grid是否含有0，如果有0，返回0。

代码

核心代码

class Solution {
		public:
			int maxProductPath(vector<vector<int>>& grid) {
				const int R = grid.size();
				const int C = grid[0].size();
				vector<vector<vector<long long>>> dp(R, vector<vector<long long>>(C,vector<long long>(2,-1)));
				auto Add = [&](int r, int c, long long value) {
					if (value < 0) {
						dp[r][c][1] = max(dp[r][c][1], -value);
					}
					else {
						dp[r][c][0] = max(dp[r][c][0], value);
					}
				};
				Add(0, 0, grid[0][0]);
				for (int dis = 0; dis < R + C - 2; dis++) {
					for (int r = max(0,dis-(C-1)); (r <= dis) && (r < R) ; r++) {
						const int c = dis - r;
						for (int k = 0; k < 2; k++) {
							const auto pre =  dp[r][c][k];
							if (-1 == pre)continue;
							int sign = (0 == k ? 1 : -1);
							if (r + 1 < R) {
								Add(r + 1, c, sign * pre * grid[r + 1][c]);
							}
							if (c + 1 < C) {
								Add(r , c + 1, sign * pre * grid[r ][c + 1]);
							}
						}
					}
				}
				long long ans = dp.back().back()[0];
				if (-1 == ans) {
					for (const auto& v : grid) {
						if (count(v.begin(), v.end(), 0)) { return 0; }
					}
				}
				return ans % ((long long)1e9 + 7);
			}
		};

单元测试

vector<vector<int>> grid;
		TEST_METHOD(TestMethod11)
		{
			grid = { {-1,-2,-3},{-2,-3,-3},{-3,-3,-2} };
			auto res = Solution().maxProductPath(grid);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			grid = { {1,-2,1},{1,-2,1},{3,-4,1} };
			auto res = Solution().maxProductPath(grid);
			AssertEx(8, res);
		}
		TEST_METHOD(TestMethod13)
		{
			grid = { {1,3},{0,-4} };
			auto res = Solution().maxProductPath(grid);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod14)
		{
			grid = { {-1,3,0},{3,-2,3},{-1,1,-4} };
			auto res = Solution().maxProductPath(grid);
			AssertEx(0, res);
		}