Chương trình tìm tích không âm lớn nhất trên đường đi trong ma trận trong Python

Ma trận m x n. Từ (0,0) đến (m-1,n-1), chỉ đi phải/xuống. Tìm đường có tích không âm lớn nhất. Trả về modulo 10⁹+7, -1 nếu không có tích không âm.

Ví dụ: [[2,-4,2],[2,-4,2],[4,-8,2]] → 256. Đường: 2→2→(-4)→(-8)→2 = 256.

Giải thuật (DP lưu max/min tích đến mỗi ô)

1. dp[i][j] = [max_prod, min_prod] đến ô (i,j).
2. Khởi tạo dp[0][0] = [val, val].
3. Điền hàng 0, cột 0: nhân tích lũy.
4. Ô còn lại: từ trên và trái, nhân với matrix[i][j], lấy max/min của 4 giá trị.
   • Nếu max < 0: cả 2 = min (tích luôn âm).
   • Nếu min > 0: cả 2 = max (tích luôn dương).
   • Ngược lại: max, min như tính.
5. Kết quả: dp[m-1][n-1][0] nếu ≥ 0 else -1.

Ví dụ minh họa

def solve(matrix):
    p = 10**9 + 7
    m, n = len(matrix), len(matrix[0])
    dp = [[[0,0] for _ in range(n)] for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[i][j] = [matrix[i][j], matrix[i][j]]
            elif i == 0:
                ans1 = dp[i][j-1][0] * matrix[i][j]
                dp[i][j] = [ans1, ans1]
            elif j == 0:
                ans1 = dp[i-1][j][0] * matrix[i][j]
                dp[i][j] = [ans1, ans1]
            else:
                ans1 = dp[i-1][j][0] * matrix[i][j]
                ans2 = dp[i-1][j][1] * matrix[i][j]
                ans3 = dp[i][j-1][0] * matrix[i][j]
                ans4 = dp[i][j-1][1] * matrix[i][j]
                maximum = max(ans1, ans2, ans3, ans4)
                minimum = min(ans1, ans2, ans3, ans4)
                if maximum < 0:
                    dp[i][j] = [minimum, minimum]
                elif minimum > 0:
                    dp[i][j] = [maximum, maximum]
                else:
                    dp[i][j] = [maximum, minimum]
    if dp[m-1][n-1][0] < 0:
        return -1
    return dp[m-1][n-1][0] % p

matrix = [[2,-4,2],[2,-4,2],[4,-8,2]]
print(solve(matrix))

Đầu vào

[[2,-4,2],[2,-4,2],[4,-8,2]]

Đầu ra

256