Dynamic Programming Bottom Up approach

help
1

There’s a question
Given an array ARR
In each turn (from 1 to N , until array is deleted),
you can either Delete 1st element or Last element of that array and multiply it by turn number and ADD the max element present in the array.
You keep doing it until array id completely deleted and Print the total number

For example
Arr = 5 4 3 6 2
Answer = 96

Explanation
2 * 1 + 6 = 8

5 * 2 + 6 = 16

3 * 4 + 6 = 18

4 * 3 + 6 = 18

6 * 5 + 6 = 36

I did the solution by using Dynamic Programming Top Down approach as

int topDown(int i,int j,int a[],int turn){
	if(i>j) return 0;
	if(dp[i][j]!=-1) return dp[i][j];

	int x = ((a[i]*turn) + RMQ(i,j)) + topDown(i+1,j,a,turn+1);
	int y = ((a[j]*turn) + RMQ(i,j)) + topDown(i,j-1,a,turn+1);
	return dp[i][j] = max(x,y);
}
int ans = topDown(0,n-1,ARR,1);

RMQ is Range Max Query with a Sparse Table of ARR O(1) TC
Can anyone Help me finding a Bottom UP approach to this solution?

2 
//base cases
//intialize all as -INF first
//assuming 1-based index

for(int j=0;j<=n;j++){ dp[j][0] = 0;}

for(int i=1;i<=n;i++){ //length i
    for(int j=1;j<=n;j++){ // start j, end j+i-1

        if(j+i-1 > n) break;
        int x = -INF, y = -INF;
        if(j < n){
            x = a[j]*(n-i+1) + RMQ(j,j+i-1) + dp[i-1][j+1];
        }
        int y = a[j+i-1]*(n-i+1) + RMQ(j, j+i-1) + dp[i-1][j]; 
        dp[i][j] = max(x, y);
    }
}
1 Like
3

Can you elaborate a little where is the final solution in dp array?

4

@snow6lade Is this question available on any online judge? Please share the link if it is. I want to test if my approach is correct or not. Thanks!

5

Oh sorry, i thought it was obvious, answer is dp[n][1]
i.e., starting at 1 and length n

6

This came in Infytq upgradation test

7

Oh ok :+1: