Chương trình tìm tích số không âm tối đa trong ma trận bằng Python

Giả sử chúng ta có một ma trận bậc m x n. Ban đầu, chúng ta đang ở ô góc trên cùng bên trái (0, 0) và trong mỗi bước, chúng ta chỉ có thể di chuyển sang phải hoặc xuống trong ma trận. Bây giờ trong số tất cả các đường đi từ ô góc trên cùng bên trái (0, 0) đến ô góc dưới cùng bên phải (m-1, n-1), chúng ta phải tìm đường dẫn có tích không âm lớn nhất. Nếu câu trả lời quá lớn, thì trả về mô-đun sản phẩm không âm tối đa 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như

2	-4	2
2	-4	2
4	-8	2

thì đầu ra sẽ là 256 vì đường dẫn có màu,

2	-4	2
2	- 4	2
4	- 8	2

vì vậy sản phẩm là [2 * 2 * (-4) * (-8) * 2] =256.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

p:=10 ^ 9 + 7
m:=số hàng của ma trận
n:=số cột của ma trận
dp:=ma trận 2d có thứ tự với ma trận đã cho và điền bằng 0
đối với tôi trong phạm vi từ 0 đến m - 1, thực hiện
- đối với j trong phạm vi từ 0 đến n - 1, thực hiện
  - nếu tôi giống 0 và j giống 0, thì
    - dp [i, j]:=tạo một cặp (ma trận [i, j], ma trận [i, j])
  - ngược lại, khi tôi giống 0, thì
    - ans1:=dp [i, j-1, 0] * ma trận [i, j]
    - dp [i, j]:=tạo một cặp (ans1, ans1)
  - ngược lại khi j giống 0 thì
    - ans1:=dp [i-1, j, 0] * ma trận [i, j]
    - dp [i, j]:=tạo một cặp (ans1, ans1)
  - nếu không,
    - ans1:=dp [i-1, j, 0] * ma trận [i, j]
    - ans2:=dp [i-1, j, 1] * ma trận [i, j]
    - ans3:=dp [i, j-1, 0] * ma trận [i, j]
    - ans4:=dp [i, j-1, 1] * ma trận [i, j]
    - tối đa:=tối đa ans1, ans2, ans3 và ans4
    - tối thiểu:=tối thiểu ans1, ans2, ans3 và ans4
    - nếu tối đa <0, thì
      - dp [i, j]:=tạo thành một cặp (tối thiểu, tối thiểu)
    - ngược lại khi tối thiểu> 0, thì
      - dp [i, j]:=tạo một cặp (tối đa, tối đa)
    - nếu không,
      - dp [i, j]:=tạo một cặp (tối đa, tối thiểu)
nếu dp [m-1, n-1, 0] <0, thì
- trả về -1
nếu không,
- trả về dp [m-1, n-1, 0]% p

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def solve(matrix):
   p = 1e9+7
   m = len(matrix)
   n = len(matrix[0])

   dp = [[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
   else:
      return int(dp[m-1][n-1][0] % p)

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

Đầu vào

"pqpqrrr"

Chương trình tìm tích số không âm tối đa trong ma trận bằng Python

Ví dụ

Đầu vào

Đầu ra