📘 題目敘述
給你一個 m x n 的矩陣 grid。一開始我站在左上角 (0, 0)，每一步只能往右或往下走。
在所有從左上角 (0, 0) 走到右下角 (m - 1, n - 1) 的路徑中，請找出乘積最大且非負的那條路徑。
一條路徑的乘積，指的是路徑上所有格子的數值全部相乘。
請回傳這個最大非負乘積對 10^9 + 7 取模後的結果。
如果最大乘積是負數，請回傳 -1。
注意：要先得到真正的最大乘積，再做取模。
條件限制
m == grid.lengthn == grid[i].length1 <= m, n <= 15-4 <= grid[i][j] <= 4
🧠 解題思路
這題的重點是：
因為格子裡可能有負數，所以「目前最大的乘積」乘上一個負數之後，反而可能變成很小；相反地，「目前最小的乘積」乘上一個負數之後，反而可能翻成很大。
所以我不能只記一個最大值，而是要同時記：
- 走到某格時，最大的乘積
- 走到某格時，最小的乘積
這樣之後遇到正數、負數、零時，才有辦法正確轉移。
所以我用 DP，對每個位置都維護兩個狀態：
maxmin
最後看右下角的最大值是不是非負即可。
所有變數
m：列數n：行數dp：三維 DP，dp[i][j][0]表示走到(i,j)的最大乘積，dp[i][j][1]表示走到(i,j)的最小乘積M：模數10^9 + 7nmax：目前格子(i,j)能得到的最大乘積nmin：目前格子(i,j)能得到的最小乘積a：從某個前一格的max乘上目前格子的值後得到的候選值b：從某個前一格的min乘上目前格子的值後得到的候選值
🪜 主要流程步驟
1. 先定義 DP 狀態：每格同時記最大值和最小值
我這裡讓每個位置 (i, j) 都存兩個值：
dp[i][j][0]：走到這格時可能得到的最大乘積dp[i][j][1]：走到這格時可能得到的最小乘積
之所以要同時存這兩個，是因為負數會讓大小關係翻轉。
如果只記最大值，遇到負數時就會漏掉答案。
2. 起點 (0,0) 的最大值和最小值都等於自己
dp[0][0][0] = grid[0][0];
dp[0][0][1] = grid[0][0];
一開始還沒走到別的地方，只有左上角這一格。
所以不管是最大乘積還是最小乘積，都只能是它自己。
3. 逐格做 DP，來源只會是上方或左方
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
因為題目規定每一步只能：
- 往右
- 或往下
所以走到 (i, j) 時，來源只可能是：
(i - 1, j)，也就是上方(i, j - 1)，也就是左方
4. 每到一格時，先準備這格的候選最大值和最小值
long long nmax = LLONG_MIN, nmin = LLONG_MAX;
if (i == 0 && j == 0)
continue;
對於除了起點以外的每一格，我都先設：
nmax = 很小nmin = 很大
表示我接下來要把所有可能來源算出來，更新這格真正的最大值和最小值。
起點 (0,0) 已經初始化過了，所以直接跳過。
5. 如果能從上面走下來，就把上面的 max / min 都乘進來試
如果上面存在，那我就可以從上面走到目前這格。
但因為目前格子的值可能是正數、負數或零，所以我不能只拿上面的最大值來算，還要一起考慮上面的最小值：
a = 目前值 × 上方最大乘積b = 目前值 × 上方最小乘積
然後從這兩個候選值裡更新：
- 目前格子的
nmax - 目前格子的
nmin
6. 如果能從左邊走過來，也一樣把左邊的 max / min 都試一次
這一步和上面完全一樣，只是來源改成左邊。
因為目前格子的答案可能來自：
- 上方
- 左方
所以我把兩邊所有可能都試過一次，最後保留：
- 最大的乘積
- 最小的乘積
7. 把這格真正的最大值和最小值存回 DP
dp[i][j][0] = nmax;
dp[i][j][1] = nmin;
當上方和左方的所有候選值都考慮完後，
這格的狀態就確定了：
dp[i][j][0] = nmaxdp[i][j][1] = nmin
這樣之後下一格再來時，就能拿這裡的資訊繼續轉移。
8. 為什麼一定要同時記最大值和最小值
這題最容易忽略的點就是這個。
如果目前格子值是負數，那：
- 一個很大的正數乘上它，會變成很小的負數
- 一個很小的負數乘上它，反而會變成很大的正數
所以真正的最大答案，不一定是從前一格的最大值轉過來的，
也有可能是從前一格的最小值轉過來的。
這就是為什麼這題一定要雙狀態 DP，而不能只記一個值。
9. 最後看右下角的最大值是不是非負
return dp[m - 1][n - 1][0] < 0 ? -1 : dp[m - 1][n - 1][0] % M;
右下角的 dp[m - 1][n - 1][0]，就是所有路徑中最大的乘積。
如果它還是負數，表示根本不存在非負路徑答案，所以回傳 -1。
如果它是非負數，就照題目要求對 10^9 + 7 取模後回傳。
⏱️ 複雜度
設 m = grid.length，n = grid[0].length。
- 時間複雜度：
O(mn)- 每個格子都只會被處理一次，每次轉移只看上方和左方。
- 空間複雜度：
O(mn)- 需要一個
m x n x 2的 DP 陣列來記錄最大值和最小值。
- 需要一個
💻 程式碼實作
class Solution {
public:
int maxProductPath(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<vector<long long>>> dp(
m, vector<vector<long long>>(
n, vector<long long>(2))); // 0是max,1是min
const int M = 1e9 + 7;
dp[0][0][0] = grid[0][0];
dp[0][0][1] = grid[0][0];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
long long nmax = LLONG_MIN, nmin = LLONG_MAX;
if (i == 0 && j == 0)
continue;
if (i > 0) {
long long a = 1LL * grid[i][j] * dp[i - 1][j][0];
long long b = 1LL * grid[i][j] * dp[i - 1][j][1];
nmax = max(nmax, a);
nmax = max(nmax, b);
nmin = min(nmin, a);
nmin = min(nmin, b);
}
if (j > 0) {
long long a = 1LL * grid[i][j] * dp[i][j - 1][0];
long long b = 1LL * grid[i][j] * dp[i][j - 1][1];
nmax = max(nmax, a);
nmax = max(nmax, b);
nmin = min(nmin, a);
nmin = min(nmin, b);
}
dp[i][j][0] = nmax;
dp[i][j][1] = nmin;
}
}
return dp[m - 1][n - 1][0] < 0 ? -1 : dp[m - 1][n - 1][0] % M;
}
};
🔗 題目連結
https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/