How do I convert this recursion into iterative DP?

Question

I am trying to solve this problem :TRT. Here is what I have done so far: I designed a recursion for given problem and used memoization to get the solution accepted.

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));
}

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 ?

Edit: My bottom up DP solution based on Tempux's explanation:

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];
}

Saeid Saeid · Accepted Answer · 2016-09-29T10:58:17

Generally you just have to fill the values that are independent first (base cases). Then fill the values that are dependent on the values you have filled before.

In this case when l==r you have an independent value. So you just fill these first: [0][0] [1][1] [2][2] ... [n-1][n-1].

Now you can see that value of [l][r] is dependent on [l+1][r] and [l][r-1]. So now you can fill the values of [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
....

So now you recognize a pattern. You can fill the whole table if you proceed diagonally.

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

Here is one possible implementation:

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] );
        }
    }
}

How do I convert this recursion into iterative DP?

1 Answers