title: How do I convert this recursion into iterative DP?
body: <p>I am trying to solve this problem :<a href="http://www.spoj.com/problems/TRT/" rel="nofollow" title=" SPOJ TRT">TRT</a>.
  Here is what I have done so far:
  I designed a recursion for given problem and used memoization to get the solution accepted. </p>
  
  <pre><code>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));
  }
  </code></pre>
  
  <p>I am trying to solve this problem by bottom up dynamic programming but I can't think of the approach, this happens with most of the dynamic programming problems I am solving , I am able to design the recursion but fail at building the iterative dp. Can someone please help me with the approach to iterative dp solution once I have figured out the recursion ?</p>
  
  <p>Edit: My bottom up DP solution based on Tempux's explanation:</p>
  
  <pre><code>int solve()
  {
     REP(i,n)
     {
        dp[i][i]=n*a[i];
     }
     REPP(i,1,n)
     {
          for(int j=0;j+i&lt;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];
  }
  </code></pre>