Maximum Non Negative Product in a Matrix (LeetCode 1594)
Đề bài
LeetCode 1594 – Maximum Non Negative Product in a Matrix (Tích không âm lớn nhất trong ma trận) – độ khó Medium.
Cho ma trận grid kích thước rows x cols. Ban đầu bạn đứng ở góc trên bên trái $(0, 0)$, và ở mỗi bước bạn chỉ được đi sang phải hoặc đi xuống trong ma trận.
Trong tất cả các đường đi bắt đầu từ góc trên bên trái $(0, 0)$ và kết thúc ở góc dưới bên phải $(rows - 1, cols - 1)$, hãy tìm đường đi có tích không âm lớn nhất. Tích của một đường đi là tích của tất cả các số nguyên trong các ô mà đường đi đi qua.
Trả về tích không âm lớn nhất modulo $10^9 + 7$. Nếu tích lớn nhất là số âm thì trả về -1.
Lưu ý rằng phép lấy modulo được thực hiện sau khi đã tìm được tích lớn nhất.
Ràng buộc:
- $1 \le rows, cols \le 15$
- $-4 \le$
grid[i][j]$\le 4$
Các ví dụ (ô tô xanh là đường đi cho tích không âm lớn nhất – trong đề gốc là các số in đậm):
Ví dụ 1:
Input: grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
Output: -1Giải thích: không thể có tích không âm trên đường đi từ $(0, 0)$ đến $(2, 2)$, nên trả về $-1$.
Ví dụ 2:
Input: grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
Output: 8Giải thích: tích không âm lớn nhất là đường được tô ($1 \times 1 \times (-2) \times (-4) \times 1 = 8$).
Ví dụ 3:
Input: grid = [[1,3],[0,-4]]
Output: 0Giải thích: tích không âm lớn nhất là đường được tô ($1 \times 0 \times (-4) = 0$).
Ví dụ 4:
Input: grid = [[1,4,4,0],[-2,0,0,1],[1,-1,1,1]]
Output: 2Giải thích: tích không âm lớn nhất là đường được tô ($1 \times (-2) \times 1 \times (-1) \times 1 \times 1 = 2$).
1594. Maximum Non Negative Product in a Matrix – Medium
You are given a rows x cols matrix grid. Initially, you are located at the top-left corner (0, 0), and in each step, you can only move right or down in the matrix.
Among all possible paths starting from the top-left corner (0, 0) and ending in the bottom-right corner (rows - 1, cols - 1), find the path with the maximum non-negative product. The product of a path is the product of all integers in the grid cells visited along the path.
Return the maximum non-negative product modulo $10^9 + 7$. If the maximum product is negative return -1.
Notice that the modulo is performed after getting the maximum product.
Example 1:
Input: grid = [[-1,-2,-3],
[-2,-3,-3],
[-3,-3,-2]]
Output: -1
Explanation: It's not possible to get non-negative product in the path from (0, 0) to (2, 2), so return -1.Example 2:
Input: grid = [[1,-2,1],
[1,-2,1],
[3,-4,1]]
Output: 8
Explanation: Maximum non-negative product is in bold (1 * 1 * -2 * -4 * 1 = 8).Example 3:
Input: grid = [[1, 3],
[0,-4]]
Output: 0
Explanation: Maximum non-negative product is in bold (1 * 0 * -4 = 0).Example 4:
Input: grid = [[ 1, 4,4,0],
[-2, 0,0,1],
[ 1,-1,1,1]]
Output: 2
Explanation: Maximum non-negative product is in bold (1 * -2 * 1 * -1 * 1 * 1 = 2).Constraints:
1 <= rows, cols <= 15-4 <= grid[i][j] <= 4
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
class Solution. Để các bạn chạy thử được trên máy (hoặc trang Chạy code online), mọi code trong bài đều có thêm hàm main đọc từ bàn phím theo định dạng: dòng đầu là hai số $rows$ và $cols$, tiếp theo là $rows$ dòng, mỗi dòng $cols$ số của grid; in ra một số là đáp án. Ví dụ 2 của đề viết thành:
3 3
1 -2 1
1 -2 1
3 -4 18.Tóm tắt đề bài: bạn được cho một ma trận kích thước $N \times M$, ô ở hàng $i$ và cột $j$ gọi là ô $(i, j)$ và có giá trị là grid[i][j]. Bạn hiện tại đang đứng tại ô $(0, 0)$, mỗi lần di chuyển, bạn chỉ được phép di chuyển sang phải hoặc xuống dưới. Hãy làm sao để có thể đến được ô $(N - 1, M - 1)$ sao cho tích của các số trên đường đi là lớn nhất và phải là một số nguyên không âm. Nếu như không tồn tại một đường đi có tích là số nguyên không âm thì trả về $-1$, ngược lại thì trả về tích có giá trị lớn nhất. Vì tích khá lớn nên ta đưa ra kết quả mod cho $10^9 + 7$.
Ví dụ 2 cho dễ hình dung: đường $1 \to 1 \to -2 \to -4 \to 1$ có hai số âm nên tích dương $= 8$. Còn đường đi thẳng hàng trên $1 \to -2 \to 1 \to 1 \to 1$ chỉ có một số âm nên tích $= -2$ (âm, không tính). Ví dụ 1 thì đường nào cũng đi qua đúng 5 ô toàn số âm ⇒ tích luôn âm ⇒ đáp án $-1$.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn mọi đường đi – O(C(n+m−2, n−1))
Cách tự nhiên nhất: đệ quy từ ô $(0, 0)$, mỗi bước thử đi xuống hoặc sang phải, mang theo tích hiện tại. Tới ô cuối thì cập nhật tích lớn nhất. Cuối cùng nếu tích lớn nhất âm thì trả về $-1$, ngược lại trả về tích đó mod $10^9 + 7$.
Số đường đi là $C(n + m - 2, n - 1)$; với $n = m = 15$ là $C(28, 14) \approx 4 \cdot 10^7$ đường. Cách này dùng để kiểm tra kết quả cho cách 2, và giúp các bạn thấy rõ vì sao cần QHĐ.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int n, m;
long long best;
void go(vector<vector<int>>& a, int i, int j, long long prod) {
prod *= a[i][j];
if (i == n - 1 && j == m - 1) { // tới ô cuối: cập nhật kết quả
best = max(best, prod);
return;
}
if (i + 1 < n) go(a, i + 1, j, prod); // đi xuống
if (j + 1 < m) go(a, i, j + 1, prod); // sang phải
}
int maxProductPath(vector<vector<int>>& a) {
n = (int) a.size();
m = (int) a[0].size();
best = LLONG_MIN;
go(a, 0, 0, 1);
if (best < 0) return -1;
return best % 1000000007;
}
};
int main() {
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cin >> a[i][j];
Solution sol;
cout << sol.maxProductPath(a) << "\n";
}
return 0;
}import sys
from typing import List
sys.setrecursionlimit(10000)
class Solution:
def maxProductPath(self, a: List[List[int]]) -> int:
n, m = len(a), len(a[0])
best = None
def go(i, j, prod):
nonlocal best
prod *= a[i][j]
if i == n - 1 and j == m - 1: # tới ô cuối: cập nhật kết quả
if best is None or prod > best:
best = prod
return
if i + 1 < n:
go(i + 1, j, prod) # đi xuống
if j + 1 < m:
go(i, j + 1, prod) # sang phải
go(0, 0, 1)
if best < 0:
return -1
return best % 1000000007
def main():
data = sys.stdin.read().split()
t = int(data[0])
p = 1
for _ in range(t):
n, m = int(data[p]), int(data[p + 1])
a = [[int(data[p + 2 + i * m + j]) for j in range(m)] for i in range(n)]
p += 2 + n * m
print(Solution().maxProductPath(a))
main()Cách 2Quy hoạch động lưu 3 trạng thái – O(N·M)
Vì sao chỉ lưu tích lớn nhất là không đủ?
Bài quen thuộc "đường đi có tổng lớn nhất" thì mỗi ô chỉ cần lưu tổng lớn nhất. Nhưng với tích thì có số âm: một tích âm rất bé (ví dụ $-32$) nhân với một số âm ($-4$) lại thành tích dương rất lớn ($128$). Nên ở mỗi ô ta phải lưu thêm cả tích âm bé nhất, và tách riêng trường hợp tích bằng 0.
Định nghĩa trạng thái
Gọi dp[i][j][type] là tích của đường đi từ ô $(0, 0)$ đến ô $(i, j)$, trong đó type thể hiện trạng thái đường đi khi đến ô $(i, j)$ hiện tại:
type = 0: tích các số trên đường đi là số âm,dp[i][j][0]lưu tích bé nhất. Ta cần tích âm bé nhất để khi gặp số âm, chuyển sang số dương, ta được tích lớn nhất.type = 1: tích các số trên đường đi là số dương,dp[i][j][1]lưu tích lớn nhất.type = 2:dp[i][j][2] = 0nếu có đường từ $(0, 0)$ đến $(i, j)$ đi qua số 0 (tích bằng 0).
Giá trị "chưa có" (hàm nonValue(type) trong code): dp[i][j][0] = +∞, dp[i][j][1] = −∞, dp[i][j][2] = −1. Khởi tạo ô đầu: nếu $a[0][0] \lt 0$ thì dp[0][0][0] = a[0][0]; nếu $a[0][0] = 0$ thì dp[0][0][2] = 0; nếu $a[0][0] \gt 0$ thì dp[0][0][1] = a[0][0].
Chuyển trạng thái (kiểu "đẩy" sang ô kế tiếp)
Với mỗi dp[i][j][type] đã có giá trị, ta có 2 tình huống là đến $(i + 1, j)$ hoặc $(i, j + 1)$. Giả sử đến ô $(i + 1, j)$ có giá trị $x = a[i + 1][j]$, ta xét $x$ là 0, âm hay dương:
- $x = 0$ (hoặc
type = 2, tức đường đã có số 0): tích bằng 0 ⇒dp[i+1][j][2] = 0. - $x \lt 0$: đổi dấu. Tích âm (type 0) thành tích dương ⇒
dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][0] * x); tích dương (type 1) thành tích âm ⇒dp[i+1][j][0] = min(dp[i+1][j][0], dp[i][j][1] * x). - $x \gt 0$: giữ dấu. Type 0 ⇒
dp[i+1][j][0] = min(..., dp[i][j][0] * x); type 1 ⇒dp[i+1][j][1] = max(..., dp[i][j][1] * x).
Ta thực hiện tương tự với ô $(i, j + 1)$.
Kết quả: nếu dp[n-1][m-1][1] có giá trị (có đường tích dương) thì trả về nó mod $10^9 + 7$; ngược lại nếu dp[n-1][m-1][2] có giá trị (có đường tích 0) thì trả về $0$; còn lại trả về $-1$ vì không tồn tại đường có tích bằng 0 hoặc tích dương.
Em nhập lưới (các hàng cách nhau bởi dấu ;) rồi bấm Tiếp để xem từng ô "đẩy" giá trị sang ô bên dưới và bên phải. Trong mỗi ô: số lớn là $a[i][j]$, dòng − là tích âm bé nhất, + là tích dương lớn nhất, 0 là có đường tích 0:
Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé:
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long inf = 100000000000000007LL;
long long dp[16][16][3];
class Solution {
public:
long long nonValue(int type) {
if (type == 0) {
return inf;
}
else if (type == 1) {
return -inf;
}
else {
return -1;
}
}
int maxProductPath(vector<vector<int>>& a) {
int n = (int) a.size();
int m = (int) a[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int type = 0; type <= 2; type++) {
dp[i][j][type] = nonValue(type);
}
}
}
if (a[0][0] < 0) {
dp[0][0][0] = a[0][0];
}
else if (a[0][0] == 0) {
dp[0][0][2] = 0;
}
else {
dp[0][0][1] = a[0][0];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int type = 0; type <= 2; type++) {
if (dp[i][j][type] == nonValue(type)) {
continue;
}
if (i < n - 1) {
if (a[i + 1][j] == 0) {
dp[i + 1][j][2] = 0;
}
else if (a[i + 1][j] < 0) {
if (type == 0) {
dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j][type] * a[i + 1][j]);
}
else if (type == 1) {
dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][type] * a[i + 1][j]);
}
else {
dp[i + 1][j][2] = 0;
}
}
else {
if (type == 0) {
dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][type] * a[i + 1][j]);
}
else if (type == 1) {
dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j][type] * a[i + 1][j]);
}
else {
dp[i + 1][j][2] = 0;
}
}
}
if (j < m - 1) {
if (a[i][j + 1] == 0) {
dp[i][j + 1][2] = 0;
}
else if (a[i][j + 1] < 0) {
if (type == 0) {
dp[i][j + 1][1] = max(dp[i][j + 1][1], dp[i][j][type] * a[i][j + 1]);
}
else if (type == 1) {
dp[i][j + 1][0] = min(dp[i][j + 1][0], dp[i][j][type] * a[i][j + 1]);
}
else {
dp[i][j + 1][2] = 0;
}
}
else {
if (type == 0) {
dp[i][j + 1][0] = min(dp[i][j + 1][0], dp[i][j][type] * a[i][j + 1]);
}
else if (type == 1) {
dp[i][j + 1][1] = max(dp[i][j + 1][1], dp[i][j][type] * a[i][j + 1]);
}
else {
dp[i][j + 1][2] = 0;
}
}
}
}
}
}
if (dp[n - 1][m - 1][1] != -inf) {
return dp[n - 1][m - 1][1] % MOD;
}
if (dp[n - 1][m - 1][2] != -1) {
return 0;
}
return -1;
}
};
int main() {
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cin >> a[i][j];
Solution sol;
cout << sol.maxProductPath(a) << "\n";
}
return 0;
}import sys
from typing import List
MOD = 1000000007
INF = 10 ** 18
class Solution:
# type 0: tích âm (lưu tích bé nhất), type 1: tích dương (lưu tích lớn nhất),
# type 2: đường đi có số 0 (tích = 0)
def nonValue(self, t: int) -> int:
if t == 0:
return INF
elif t == 1:
return -INF
return -1
def maxProductPath(self, a: List[List[int]]) -> int:
n, m = len(a), len(a[0])
dp = [[[self.nonValue(t) for t in range(3)] for _ in range(m)] for _ in range(n)]
if a[0][0] < 0:
dp[0][0][0] = a[0][0]
elif a[0][0] == 0:
dp[0][0][2] = 0
else:
dp[0][0][1] = a[0][0]
for i in range(n):
for j in range(m):
for t in range(3):
if dp[i][j][t] == self.nonValue(t):
continue
for x, y in ((i + 1, j), (i, j + 1)): # xuống dưới, sang phải
if x >= n or y >= m:
continue
v = a[x][y]
if v == 0 or t == 2:
dp[x][y][2] = 0
elif v < 0:
if t == 0:
dp[x][y][1] = max(dp[x][y][1], dp[i][j][t] * v)
else:
dp[x][y][0] = min(dp[x][y][0], dp[i][j][t] * v)
else:
if t == 0:
dp[x][y][0] = min(dp[x][y][0], dp[i][j][t] * v)
else:
dp[x][y][1] = max(dp[x][y][1], dp[i][j][t] * v)
if dp[n - 1][m - 1][1] != -INF:
return dp[n - 1][m - 1][1] % MOD
if dp[n - 1][m - 1][2] != -1:
return 0
return -1
def main():
data = sys.stdin.read().split()
t = int(data[0])
p = 1
for _ in range(t):
n, m = int(data[p]), int(data[p + 1])
a = [[int(data[p + 2 + i * m + j]) for j in range(m)] for i in range(n)]
p += 2 + n * m
print(Solution().maxProductPath(a))
main()for x, y in ((i + 1, j), (i, j + 1)) và gộp trường hợp "ô kế là 0" với "đường đã có 0" làm một, nên ngắn hơn bản C++. Số nguyên Python không giới hạn nên không lo tràn số.Em bấm Tiếp trong khung chạy tay dưới đây để xem từng dòng code C++ chạy. Khung "Dữ liệu" vẽ lưới $a$ và 3 bảng dp[.][.][0] (tích âm bé nhất), dp[.][.][1] (tích dương lớn nhất), dp[.][.][2] (có đường tích 0); ô "·" là chưa có giá trị. Để khung chạy tay không quá dài, phần khởi tạo bằng nonValue được gom mỗi ô một bước:
Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng
dpcó $N \cdot M \cdot 3$ phần tử ⇒ $O(N \cdot M)$. - Thời gian: mỗi ô, mỗi trạng thái đẩy sang tối đa 2 ô kế tiếp ⇒ $O(N \cdot M)$.
long long (khoảng $9{,}2 \cdot 10^{18}$).inf = 10^17 + 7 ở đây chỉ đóng vai trò "dấu hiệu chưa có giá trị" (so sánh bằng với nonValue(type)). Tích thật có thể vượt $10^{17}$ (tới $4^{29}$) nhưng code vẫn đúng, vì tích luôn có dạng $\pm 2^x 3^y$ nên không bao giờ trùng đúng giá trị $\pm(10^{17} + 7)$, còn phép max/min với giá trị khởi tạo vẫn chọn đúng tích thật. Bạn nào muốn chắc ăn hơn có thể đặt inf = 4e18.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét