この再帰を反復DPに変換するにはどうすればよいですか？

Question

私はこの問題を解決しようとしています：TRT。 ここまで私がこれまで行ってきたことは次のとおりです。 解決策を受け入れるために、問題の再帰を設計してメモを使用しました。

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]。

今すぐ[L] [R]がに依存している[L + 1] [R]と[L] [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]); 
     } 
    } 
}