資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python 矩陣中最大非負積的程式
假設我們有一個m x n階矩陣。我們最初位於左上角單元格(0, 0)，每一步只能在矩陣中向右或向下移動。現在，在從左上角單元格(0, 0)到右下角單元格(m-1, n-1)的所有可能路徑中，我們必須找到具有最大非負積的路徑。如果答案太大，則返回最大非負積模10^9+7。
因此，如果輸入如下所示：
| 2 | -4 | 2 |
| 2 | -4 | 2 |
| 4 | -8 | 2 |
那麼輸出將是256，因為路徑是彩色的那條，
| 2 | -4 | 2 |
| 2 | -4 | 2 |
| 4 | -8 | 2 |
所以乘積是 [2 * 2 * (-4) * (-8) * 2] = 256。
為了解決這個問題，我們將遵循以下步驟：
- p := 10^9+7
- m := 矩陣的行數
- n := 矩陣的列數
- dp := 一個與給定矩陣同階的二維矩陣，並填充0
- 對於 i 從 0 到 m - 1：
- 對於 j 從 0 到 n - 1：
- 如果 i 等於 0 且 j 等於 0，則
- dp[i, j] := 建立一個 (matrix[i, j], matrix[i, j]) 對
- 否則，如果 i 等於 0，則
- ans1 := dp[i, j-1, 0] * matrix[i, j]
- dp[i, j] := 建立一個 (ans1, ans1) 對
- 否則，如果 j 等於 0，則
- ans1 := dp[i-1, j, 0] * matrix[i, j]
- dp[i, j] := 建立一個 (ans1, ans1) 對
- 否則，
- 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 := ans1, ans2, ans3 和 ans4 的最大值
- minimum := ans1, ans2, ans3 和 ans4 的最小值
- 如果 maximum < 0，則
- dp[i, j] := 建立一個 (minimum, minimum) 對
- 否則，如果 minimum > 0，則
- dp[i, j] := 建立一個 (maximum, maximum) 對
- 否則，
- dp[i, j] := 建立一個 (maximum, minimum) 對
- 如果 i 等於 0 且 j 等於 0，則
- 對於 j 從 0 到 n - 1：
- 如果 dp[m-1, n-1, 0] < 0，則
- 返回 -1
- 否則，
- 返回 dp[m-1, n-1, 0] % p
示例
讓我們看看下面的實現以更好地理解：
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))
輸入
"pqpqrrr"
輸出
256
更新於：2021年10月4日
瀏覽量：133
廣告