【C++动态规划】1594. 矩阵的最大非负积|1807

本文涉及知识点

下载及打开打包代码的方法兼述单元测试
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)后续单格。
$\begin{cases} dp[r1][r1][0] \times grid[r][c] \\ -dp[r1][r1][1] \times grid[r][c] \\ \end{cases}$
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);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功