給定下面的數據，找到從左下角到右上角的最高價值路線。[{ 0, 0, 0, 6 }, { 2, 0, 0, 2 }, { 0, 1, 1, 1 }, { 3, 0, 0, 0 }]go can only move right (east) or up (north)Highest value route here is 3 -> 0 -> 1 -> 1 -> 1 -> 2 ->6 = 14我應該如何處理這個問題。我下面作為偽代碼的方法是否正確？max = 0array = defined_array i = len(array)k = 0 def path(i,j):total = 0 for j in range(4): k = j; total = total + int(array[i][j]) if total > max: max = total return path(--i,k)key= 3def path(i,j): for i in range(i): for j in range(array[i]): total = total + array[i][j]
2 回答
守著一只汪
TA貢獻1872條經驗 獲得超4個贊
我根本沒有得到你的方法。
這就是簡單動態規劃問題。
將其視為二維數組Arr[4][4]
[{ 0, 0, 0, 6 },
{ 2, 0, 0, 2 },
{ 0, 1, 1, 1 },
{ 3, 0, 0, 0 }]
制作另一個 4*4 的 dp 數組
您需要做的第一件事是初始化基本案例。
所以第一列和最后一行是我們的基本情況。
dp[0][3]=Arr[0][3];
在此之后為第一列
dp[i][0]=dp[i+1][0]+Arr[i][0];
對于最后一行
dp[3][i]=dp[3][i-1]+Arr[3][i];
對于其他值
dp[i][j]=max(dp[i][j-1],dp[i+1][j])+Arr[i][j];
，我們將選擇最大值。
我們的 dp 數組看起來像這樣，答案是 14
[{ 5, 5, 5, 14 },
{ 5, 5, 5, 8 },
{ 3, 4, 5, 6 },
{ 3, 3, 3, 3 }]
Qyouu
TA貢獻1786條經驗 獲得超11個贊
這基本上是通過圖找到最優路徑（在這種情況下：最高值路徑）的問題。
有一些眾所周知的方法可以找到最短路徑，例如Dijkstra 算法和Bellman-Ford 算法。
對于您的圖是有向圖和無環圖（“DAG”），我在這里和這里發現了兩個討論，指出這些算法不能僅僅從最小到最大“反轉”以找到最長的路徑，但是如果你轉換你的路徑它確實有效將每個權重（值）反轉為負數的圖形。
添加回答
舉報
0/150
提交
取消