本文涉及知识点
下载及打开打包代码的方法兼述单元测试
C++动态规划
LeetCode1594. 矩阵的最大非负积
给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。
在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。
返回 最大非负积 对 109 + 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);
}
