如何将此递归转换为迭代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]); 
     } 
    } 
}