题目描述

n堆石子，每堆都有一定的质量，只能相邻两堆合并成一堆，要求合并的总代价最小。
1 <= n <= 300;

样例

输入：
4
1 3 5 2

输出：
2

算法1

(区间dp) $O(n^3)$

• 枚举每个子区间[i,j]
• 计算合并该子区间的最小代价
  • 枚举k把子区间分成两堆 : [i, k] [k + 1, j]
  • 把这左右两堆合并成1堆的最小代价为 ： 合成左堆本身需要最小代价 + 合成右堆本身需要最小代价 + 再这两堆合成在一起的代价

时间复杂度

• 外2层循环根据区间长度和区间起点枚举所有连续子区间 $O(n^2)$
• 最内层循环枚举子区间的左右分割点 $O(n)$
• 共需要$O(n^3)$

参考文献

C++ 代码

#include <iostream>

using namespace std;

const int N = 310;
int dp[N][N];
int s[n];
int n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        s[i] += s[i-1];
    }

    for(int len = 2; len <= n; len ++)
        for(int i = 1; i + len - 1 <= n; i ++)
        {
            int j = i + len -1;
            dp[i][j] = 1e8;

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

        }

    cout << dp[1][n] << endl

    return 0;

}