algorithm problem, cost of merging list of integers

Question

Let L be a list of positive integers. We are allowed to merge two elements of L if they have adjacent indices. The cost of this operation is the sum of both elements.

For example: [1,2,3,4] -> [3,3,4] with a cost of 3.

We are looking for the minimum cost to merge L into one integer.

Is there a fast way of doing this? I came up with this naive recursive approach but that should be O(n!). I have noticed that it benefits a lot from memoization so I think there must be a way to avoid trying all possible permutations which will always result in O(n!).

def solveR(l):
  if len(l) <= 2:
    return sum(l)
  else:
    return sum(l) + min(solveR(l[1:]), solveR(l[:-1]), 
           solveR(l[len(l) // 2:]) + solveR(l[:len(l) // 2]))

Answer 1

This is much like this LeetCode problem, but with K = 2. The comments suggest that the time complexity is O(n^3). Here is some C++ code that implements the algorithm:

class Solution {
public:
    int mergeStones(vector<int>& stones, int K) {
        K = 2;
        int N = stones.size();
        if((N-1)%(K-1) > 0) return -1;

        int sum[N+1] = {0};
        for(int i = 1; i <= N; i++)
            sum[i] = sum[i-1] + stones[i-1];

        vector<vector<int>> dp(N, vector<int>(N,0));

        for(int L=K; L<= N; L++)
            for(int i=0, j=i+L-1; j<N; i++,j++) {
                dp[i][j] = INT_MAX;

                for (int k = i; k < j; k += (K-1))
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);

                if ((L-1)%(K-1) == 0)
                    dp[i][j] += (sum[j+1] - sum[i]); // add sum in [i,j]
            }

    return dp[0][N-1];
}
};