如何最大化路徑的價值？

Question

我們得到一個N * N網格。我們最初在網格的左上角。網格中的每一個方格都有一定的價值，也就是說，如果有人到達那個廣場，他會贏得等於附加在廣場上的價值的美元。現在合法的舉動向右邁出了一步，或朝着底部邁出了一步。我們必須以一種方式到達電網的右下角，以便我們能夠最大限度地贏得金錢。顯然我們必須留在電網內，不能漫步。 我以一種貪婪的方法開始了這個問題，在每一步我們都看到佔用方塊下面的直接右方和直接方塊，並且在每一步選擇具有較高值的​​方塊。但是這並不總是給出正確的結果。例如，在下面的網格，

{ 6, 9, 18, 1 } 
{ 2, 10, 0, 2 } 
{ 1, 100, 1, 1 } 
{ 1, 1, 1, 1 } 

這裏我的算法給出了最大值路徑爲

6 -> 9 -> 18 -> 1 -> 2 -> 1 -> 1 

這總計37，但我們可以贏得更多的道路上

6 -> 9 -> 10 -> 100 -> 1 -> 1 -> 1 

其中總計爲128.你能幫助我建立一個合適的算法嗎？我還沒有編碼這個，因爲它會給出錯誤的輸出。我不知道如何在沒有暴力的情況下處理這個問題，這種暴力包括在所有不包含具有最小值的平方的路徑中看到值，然後找到最大值。

#include <iostream> 
#include <queue> 
using namespace std; 
int main() 
{ int n; cin >> n; 
int a[n+1][n+1], b[n+1][n+1]; 
for (int i=0;i<n;i++) 
{ 
for (int j=0;j<n;j++) 
{ 
    cin >> a[i][j]; b[i][j]=a[i][j]; 
} 
} 

queue <int> q; int u,v,m=0; 
q.push(0);q.push(0); 
while (q.size()!=0) 
{ 
    u=q.front(); q.pop(); v=q.front(); q.pop(); 
    if (v<n-1) 
    { 
     m=b[u][v]+a[u][v+1]; 
     if (m>b[u][v+1]) 
     { b[u][v+1]=m; } 
     q.push(u);q.push(v+1); 
    } 
    if (u<n-1) 
    { 
     m=b[u][v]+a[u+1][v]; 
     if (m>b[u+1][v]) 
     { b[u+1][v]=m; } 
     q.push(u+1);q.push(v); 
    } 
} 
cout << b[n-1][n-1]; 
return 0; 
} 

Answer 1

其實這是一個可以通過動態規劃解決的問題。您只需調整算法以計算編輯距離，即可獲得不同的獎勵。該算法在例如https://web.stanford.edu/class/cs124/lec/med.pdf

中描述該算法的基本思想是，您從頂部開始，每當您現在將其鄰居（頂部，左側）字段填入一個正方形時。 您在該字段中輸入的值是兩個鄰居中較高者的值和當前字段的值。當你到達右下角時，你只需要沿着路徑返回。

Answer 2

該問題可以通過以下方法解決。位置(i,j)上的每個單元格都與值val(i,j)相關聯，該值是通過從位置(0,0)開始以所描述的合法移動（到底部，到右側）到達它的可能的最大總值。位置(0,0)上的值是來自網格的值，後續稱爲grid(i,j)，每i, j in {0,...,N-1}。我們得到follwing遞推關係

val(i,j) = grid(i,j) + max{ val(i-1,j), // path coming from upper cell 
          val(i,j-1) // path coming from left cell 
          } 

，我們假設的{0,...,N-1} * {0,...N-1}外面指數產生負無窮大的價值，並從來沒有真正使用。遞歸關係是有效的，因爲最多有兩種情況到達一個單元，即從其上部鄰居或其左側鄰居（除了邊界處的單元，可能僅從一個鄰居到達）。

有效評估val的關鍵在於組織計算值的順序，以便所有需要的鄰居都已經被評估;這可以通過在最左邊的單元處連續凝視計算來完成，其中val尚未計算，並且從那裏以向上向右的方式工作，直到達到第一行。這是迭代的，直到val(N-1,N-1)被評估爲止，這產生期望的結果。

如果另外需要到(N-1,N-1)的特定路徑，則必須使用回溯或一些輔助數據結構來存儲如何計算上述遞歸關係中的值，即哪個項產生最大值。

編輯

另外，評估可以做到逐行從左向右，也有那些已經計算了遞推關係的所有必要的值所需的性能;這顯然更容易實現。無論哪種情況，運行時間綁定將爲O(n^2)。