### PROBLEM LINK:

*Author:* vinod10

*Tester:* manjunath1996

*Editorialist:* vinod10

### DIFFICULTY:

Medium

### PREREQUISITES:

Knowledge of basic DP.

### PROBLEM:

Given a sequence of N numbers, at every step a number from boundary is removed and cost associated with it is added in answer. We have to minimize the total cost.

### QUICK EXPLANATION:

We keep a 3-D array dp[i][j][k], where [i,j] is the range for which we are solving the problem and k denotes positions of previously selected elements. With memoization, we solve this dp recursively.

### EXPLANATION:

**N ^{4} approach :**

You can use 4-D array dp[i][j][k][l], where [i,j] is the range, k denotes last element selected and l denotes second last element that was selected.

Now at each step you can either select ith element or jth element, so

dp[i][j][k][l] = min( A[i] * (A[k]+1) * (A[l]+2)+ dp[i+1][j][i][k] , A[j] * (A[k]+1) * (A[l]+2)+ dp[i][j-1][j][k])

**N ^{2} approach :**

We actually don’t need to use 4-D array here, as there are only four possible value that last and second last number can take.

Assume we are currently solving for the range [i,j], then 4 possible positions for previously selected elements are :

i-1 and i-2

j+1 and j+2

i-1 and j+1

j+1 and i-1

These are the only 4 positions previous two elements can take as we are removing only boundary elements each time.

Hence a 3-D array, dp[i][j][4] can be used where [i,j] is range and third number shows positions of previously selected elements.

See the solution for more explanation.

### AUTHOR’S SOLUTIONS:

Author’s solution can be found here.