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:
N4 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])
N2 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.