Minimum Cost of Reducing Array

• It can be proved that the greedy solution will not be optimum, so we need to solve this by dp or recursion. E.g., if ‘ARR’ = {6,4,4,6} and we try to merge the elements with minimum sum first, i.e. merge 4 and 4 first and so on, we will get the answer as 42, but the optimal merging gives 40.
• The main idea is to merge two consecutive numbers at every possible index ‘i’ and then recursively call it for the left and the right parts.
• As we know for an integer at index ‘i’, it has two choices: either to merge with element on its left or to merge with element on its right. Thus we can try all possibilities, and take the minimum.
• To optimise recursion, we can memoize the results into a 2D array, so that we don’t have to recalculate the values for merging again and again.
• Let the function name be MIN_COST() which will give the minimum cost of merging, where we assume that MIN_COST(i, j) returns the optimum cost for merging elements of the array from index i to index j. Now when trying to merge from i to j, we are assuming that we have already merged the elements from 1 to i, and j to ‘N’, where ‘N’ is the size of the array, and this is why dynamic programming comes into play.
• Let us create a 2D array ‘DP[200][200]’, where ‘DP[L][R]’ will contain the minimum value of merging ‘ARR[L...R]’ into one.
• Hence after the recursion is complete, our answer will be stored at ‘DP[1][N]’.
• Let the array 'PREF_SUM' denote the prefix sum of the array ‘ARR’. So to find the sum of values from ‘ARR[L]’ to ‘ARR[R]', we can use ‘PREF_SUM[R]’ - ‘PREF_SUM[L - 1]’.
• Let us assume that we have to find the minimum cost for merging elements from ‘ARR[L]’ to ‘ARR[j]’. So let initially ‘DP[i][j]’ = infinity( ‘INT_MAX’ in C++ etc.).
• Clearly the sum of elements of the array from index ‘L’ to index ‘R’ = ‘PREF_SUM[R]’ - ‘PREF_SUM[L - 1]’.
• Since we are using recursion, we can try all the possible mergings of adjacent elements, so for the interval l to r, the number of possible mergings are ('ARR[L]', ‘ARR[L + 1]’),  ('ARR[L + 1]', ‘ARR[L + 2]’), ('ARR[L + 2]', ‘ARR[L + 3]’).... ('ARR[R - 1]
• , ‘ARR[R]’).
• After trying all the possible mergings, we can take the minimum of all and move forward. For merging the interval ‘L’ to ‘R’ in ‘ARR’, the cost of that segment will be equal to the sum of that segment.
• We can write ‘DP[L][R]' = min('PREF_SUM(L, L)' + ‘PREF_SUM(L + 1, R)’ + ‘DP[L][L]’ + ‘DP[L + 1][R]’, ‘PREF_SUM(L, L + 1)’ + ‘PREF_SUM(L + 2, R)’ + ‘DP[L][L + 1]’ + ‘DP[L + 2][R]’, …, ‘PREF_SUM(L, R – 1)’ + ‘PREF_SUM(R, R)’ + ‘DP[L][R – 1]’ + ‘DP[R][R]’)

         ‘DP[L][R]’ = S('L', ‘R’) + min('DP[L][L]' + ‘DP[L + 1][R]’, ‘DP[L][L + 1]’ + ‘DP[L + 2][R]’, …, ‘DP[L][R – 1]’ + ‘DP[R][R]’)

• Simplifying the previous statement, for ‘K’ = i to ‘K' = j-1 we can do the following to find the minimum cost:
  • ‘DP[i][j]’ = min('DP[i][j]', MIN_COST(i, k) + MIN_COST(k + 1, j) + ‘SUM’), where ‘SUM’ = ‘PREF_SUM[R]' - ‘PREF_SUM[L - 1]’, for all ‘K’ from i to j-1.

• In the previous approach, we used a top-down approach to solve the problem, in this approach we will try to build some kind of a bottom-up solution.
• The main idea is to merge two consecutive numbers at every possible index i and then do the same for the left and the right parts.
• Let us create a 2d array ‘DP[N][N]’, where each ‘DP[i][j]’ will store the minimum cost to merge the segment ‘ARR[i…j]'.
• Hence after the iteration is complete our answer will be stored at the index ‘DP[0][N-1]’.
• As mentioned above, we will try to merge all the possible segments of length 1 to ‘N’ starting from an index i, i.e. for all the lengths from 1 to ‘N’ we will try to merge the segment from i to i + ‘LEN’ and simultaneously store to find the minimum cost for that segment.
• Since we will be needing subarray sums for finding the minimum cost to merge the segments, let ‘PREF_SUM’ store the prefix sum of the array from which we can easily find the subarray sum. So to find the sum of values from ‘ARR[L]’ to ‘ARR[R]’, we can use ‘PREF_SUM[R]’ - ‘PREF_SUM[L - 1]'.
• Now for ‘LEN’ = 1 to ‘LEN’ = ‘N’ - 1 and i = 0 to i + ‘LEN’ < ‘N’, do the following:
  • Let ‘L’ = i and ‘R’ = i + ‘LEN’, which denotes the subarray ‘ARR[L]' to ‘ARR[R]’.
  • Initialize ‘DP[i][j]’ = infinity( 'INT_MAX' in C++ etc.) because initially, this would be the minimum cost before any merging.
  • Now iterate over the segment from ‘L’ to ‘R’ and find the minimum cost for merging the segment.
  • Let ‘SUM’ = ‘PREF_SUM[R]' - ‘PREF_SUM[L-1]’, denote the subarray sum of the current segment from ‘L’ to ‘R’.
  • For finding the cost of merging a given segment, We can write ‘DP[L][R]’ = min(S('L', ‘L’) + S('L' + 1, ‘R’) + ‘DP[L][L]’ + ‘DP[L + 1][R]’, S('L', ‘L’ + 1) + S('L' + 2, ‘R’) + ‘DP[L][L + 1]' + ‘DP[L + 2][R]’, …,S('L', ‘R’ – 1) + S('R', ‘R’) + ‘DP[L][R – 1]’ + ‘DP[R][R]’)

‘DP[L][R]’ = S('L', ‘R’) + min('DP[L][L]' + ‘DP[L + 1][R]’, ‘DP[L][L + 1]’ + ‘DP[L + 2][R]’, …, ‘DP[L][R – 1]’ + ‘DP[R][R]’)

• Simplifying the previous statement, for ‘K’ = i to ‘K’ = j-1 we can do the following to find the minimum cost ‘DP[L][R]’ = min('DP[L][R]', ‘DP[L][K]’ + ‘DP[k + 1][j]’ + ‘SUM’), where ‘SUM’ = ‘PREF_SUM[R]' - ‘PREF_SUM[L - 1]', for all ‘K’ from i to j-1.
• After the loop ends, our answer will be stored at ‘DP[0][N - 1]'.