如何將此遞歸轉換爲迭代DP？

Question

我想解決這個問題：TRT。 這是我迄今爲止所做的： 我爲給定的問題設計了一個遞歸，並使用memoization來接受解決方案。

int recur(int l,int r,int level) 
{ 
    if(l==r) 
     return level*a[l]; 
    if(dp[l][r]) 
     return dp[l][r]; 
    return dp[l][r]=max(level*a[l]+recur(l+1,r,level+1),level*a[r]+recur(l,r-1,level+1)); 
} 

我試圖解決由底向上的動態規劃這個問題，但我想不出辦法的，出現這種情況與大多數的我解決了動態規劃的問題，我能設計遞歸但在構建迭代dp時失敗。一旦我找到了遞歸，有人可以幫助我解決迭代dp解決方案嗎？

編輯：基於Tempux的解釋我的自下而上DP解決方案：

int solve() 
{ 
    REP(i,n) 
    { 
     dp[i][i]=n*a[i]; 
    } 
    REPP(i,1,n) 
    { 
     for(int j=0;j+i<n;j++) 
     { 
      dp[j][j+i]=max((n-i)*a[j]+dp[j+1][j+i],(n-i)*a[j+i]+dp[j][j+i-1]); 
     } 
    } 
    return dp[0][n-1]; 
} 

Answer 1

一般來說，您只需要填寫獨立於第一（基本情況）值。然後填寫取決於您之前填寫的值的值。

在這種情況下，當l == r您有一個獨立的值。所以你只需填寫這些：[0] [0] [1] [1] [2] [2] ... [n-1] [n-1]。現在

可以看到的該值[1] [R]取決於[L + 1] [R]和[1] [R-1]。所以現在你可以填寫[0] [1] [1] [2] [2] [3] ... [n] [n-1]的值。

[0][1] is dependent on [0][0] and [1][1] which you have filled before 
[1][2] is dependent on [1][1] and [2][2] which you have filled before 
.... 

所以，現在你認識到一種模式。如果您沿對角線行進，您可以填寫整個表格。

0 * * * *  0 1 * * *  0 1 2 * *  0 1 2 3 * 
* 0 * * *  * 0 1 * *  * 0 1 2 *  * 0 1 2 3 
* * 0 * *  * * 0 1 *  * * 0 1 2  * * 0 1 2 
* * * 0 *  * * * 0 1  * * * 0 1  * * * 0 1 
* * * * 0  * * * * 0  * * * * 0  * * * * 0 

這裏是一個可能的實現：

for (int d=0; d<=n-1; ++d){ 
    for (int l=0; l<=n-1; ++l){ 
     int r = l+d; 
     if (r >= n) 
      break; 
     int level = n-(r-l); 
     if (l==r){ 
      dp[l][r] = level*v[l]; 
     } else { 
      dp[l][r] = max(level*v[l] + dp[l+1][r], 
          level*v[r] + dp[l][r-1]); 
     } 
    } 
}