Need help in code logic

#1

For the solution, I have initially set i as 1 and j to n as we need to take left element and right element int o consideration for each element.

so, let’s say if we have only 1 book i.e 1 2 1… (2 being the cost and 1’s are added to left and right) . For the condition specified above, i is set to 1 and j also to 1.

To find the cost, I have used expression as arr[i-1] * arr[k] *arr[j+1]. Please let me know where I am going wrong with this approach only.

#2

Hi @PThak2018

  1. You aren’t adding the product everytime.
  2. You are supposed to use dp in this problem to store the max cost for a subset of index i to index j.
#3

Product is added every time in the loop from k=i to j-1.

I will convert this recursive code either into top-down or bottom-up approach, but need to understand the problem with this code as this is not giving the correct answer. So kindly help me with that. Please find the approach used in earlier comments.

#4

Hi @PThak2018

Once try to dry run your loop k=i to j-1. then you will be able to understand it more clearly that you aren’t adding the product everytime but you are just updating the ans by total, so it will not give you the total sum but it will give you the max value of total achieved so far.

#5

we need to return the max cost only in order to take all the books out.

The problem is with the loop and may be base condition. I will try to dry run again but getting stuck.

Using below loop and base condition, the code is working fine. But need to know how to correct the logic while using the approach of loop definition discussed earlier in the doubt.

if(i>j){
return 0;
}

if(dp[i][j]!= -1){
  return dp[i][j];
}

int ans = 0;
for(int k=i+1;k<j;k++){
  int temp1 = maxCost(arr,i,k,dp);
  int temp2 = maxCost(arr,k,j,dp);
  int total = temp1 + temp2 + arr[i]*arr[k]*arr[j];
  if(total>ans){
    dp[i][j] = ans = total;
  }
}
return ans;
#6

I have done the changes in loop and it’s working fine according to me now.
Could you please check in case I have missed any boundary condition ?

#7

@PThak2018 code seems fine but use memoization for efficiency.

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.