C++

$\color{#cc33ff}{— > 算法基础课题解}$

区间dp

$图解分析：$

图一：

图二：

时间复杂度：$O(n^3)$

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 310;

int n;
int s[N]; // 前缀和
int f[N][N]; // 状态

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

    for (int i = 1; i <= n; i ++) s[i] += s[i - 1];

    for (int len = 2; len <= n; len ++) // 从小到大枚举（循环区间长度）
        for (int i = 1; i + len - 1 <= n; i ++) { // 循环区间左端点
            int l = i, r = l + len - 1;
            f[l][r] = 1e8; // 初始化
            for (int k = l; k < r; k ++) // 枚举决策
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }

    cout << f[1][n];    
    return 0;
}