算法问题，合并整数列表的成本

Question

令L为正整数列表。如果 L 的两个元素具有相邻的索引，我们可以合并它们。此操作的成本是两个元素的总和。

例如:[1,2,3,4] -> [3,3,4]，成本为 3。

我们正在寻找将L合并为一个整数的最低成本。

有没有快速的方法来做到这一点？我想出了这种天真的递归方法，但这应该是 O(n!)。我注意到它从内存中受益匪浅，所以我认为必须有一种方法来避免尝试所有可能的排列，而这总是会导致 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

这很像LeetCode problem,但 K = 2。注释表明时间复杂度为 O(n^3)。下面是一些实现该算法的 C++ 代码:

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];
}
};