我不知道如何處理這個問題。
我們得到一個 N*N 網格，列出從位置 a 到位置 b 的成本。
網格中的每一行告訴我們從一個位置到另一個位置的成本（每個位置對應于成本陣列中的一行）。（如果行 a 出現在成本陣列中的行 b 之后，我們說位置 a 大于位置 b。每一行的索引都是一個位置）。我們可以選擇從任何給定位置開始，并且只訪問每個位置一次。在我們訪問的每個位置 p 上，我們必須已經訪問了所有小于 p 的位置，或者沒有任何小于 p 的位置。
- cost[a][b] 給出了從位置 a 移動到位置 b 的成本。
- 成本[a][b] 不一定與成本[b][a] 相同。
- 對于每個索引 a，成本 [a][a] = 0（成本陣列中的對角線始終為 0）。
我們的任務是找到有效路徑的最大總成本。
如果成本陣列是：
[[0, 9, 1],
[5, 0, 2],
[4, 6, 0]]
因此，最大成本將為 13，因為最昂貴的有效路徑從位置 2 -> 位置 0 -> 位置 1 開始。
第一行告訴我們從位置 0 到位置 0（保持在同一位置，花費我們 0）、從 0 到位置 1（花費我們 9）和 0 到位置 2（花費我們 1）需要多少。第二行和第三行遵循相同的模式。
uj5u.com熱心網友回復：
您可以訪問哪些位置的要求意味著在您從某個位置開始后i，您將被迫反復移動到較低的位置，直到到達位置 0。此時，您必須連續上升通過所有位置未訪問。動態規劃解決方案并不明顯，但通過相當復雜的實作，您可以O(n^3)使用標準技術獲得DP 演算法。
事實證明，也有一個O(n^2)解決方案，這是最佳的。它還使用O(n)額外的空間，這可能也是最佳的。解決方案來自對訪問結構的思考：有一個以 0 結尾的向下索引序列（可能有間隙），然后是一個從 0 開始包含所有其他索引的向上序列。2^n雖然有可能的子序列，所以我們必須考慮更多以加快速度。
兩個序列
假設我們有i位置，0, 1, ... i-1，并且我們已經將它們劃分為兩個有序的子序列（0 除外，它位于兩者的開頭）。我們將這兩個序列稱為U和D，分別表示向上和向下。恰好其中之一必須以 結束i-1。不失一般性，假設ü結尾i-1和d帶兩端j >= 0。
添加位置時會發生什么i？我們要么將其添加到U的末尾，以便我們的序列以iand結尾j，或者我們將其添加到D的末尾，以便我們的序列以i-1and結尾i。如果我們將其添加到ü，路徑求和ù（我們定義為的總和cost[u][v]對所有相鄰的指數u,v在ü）通過增加cost[i-1][i]。如果再加上位置結束d，的路徑和d的增加cost[i][j]（因為它是一個向下的順序，我們已經翻轉相對指數ü）。
事實證明，我們只需要在我們增長子序列時跟蹤它們的端點，以及具有這些端點的任何一對子序列的最大組合路徑和。如果我們讓(i, j)表示在狀態ü結尾i和d兩端用j，大家可以想一想我們怎么可能來到這里。
例如，在(8,5)，我們之前的狀態一定有一個包含 的子序列7，所以我們之前的狀態一定是(7,5)。因此max-value(8,5) = max-value(7,5) cost[7][8]。當兩個端點相差不止一個時，我們總是只有一個前驅狀態。
現在考慮狀態(8,7)。我們不可能來自(7,7)，因為兩個序列中唯一允許的數字是0。所以我們可以來自以下任何一個(0,7), (1,7), ... (6,7)：我們可以選擇使我們的路徑總和最大化的任何一個。
def solve(costs: List[List[int]]) -> int:
n = len(costs)
# Deal with edge cases
if n == 1:
return 0
if n == 2:
return max(costs[0][1], costs[1][0])
ups = [costs[0][1]]
downs = [costs[1][0]]
# After iteration i, ups[j] denotes the max-value of state (i, j)
# and downs[j] denotes the max-value of state (j, i)
for i in range(2, n):
ups.append(max(downs[j] costs[j][i] for j in range(i - 1)))
downs.append(max(ups[j] costs[i][j] for j in range(i - 1)))
up_gain = costs[i-1][i]
down_gain = costs[i][i-1]
for j in range(i - 1):
ups[j] = up_gain
downs[j] = down_gain
return max(max(ups), max(downs))
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/329933.html
上一篇：如何在以下代碼中使用遞回技術？