[4,5,19,23,2,8]的最优二叉搜索树，C++语言实现源码

以下是C++实现的源码，采用动态规划的思想：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int n, w[MAXN], c[MAXN][MAXN], f[MAXN][MAXN];

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

    memset(f, INF, sizeof(f));
    for (int i = 1; i <= n; i++)
        f[i][i] = c[i][i] = w[i] - w[i - 1];

    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            for (int k = i; k <= j; k++)
            {
                if (k == i) f[i][j] = min(f[i][j], f[k + 1][j] + c[i][j]);
                else if (k == j) f[i][j] = min(f[i][j], f[i][k - 1] + c[i][j]);
                else f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + c[i][j]);
            }
        }

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

代码中的 `w` 数组存储前缀和，`c[i][j]` 表示节点 `i` 到 `j` 的权值和，`f[i][j]` 表示以节点 `i` 到节点 `j` 的子树构成的二叉搜索树的最小代价。在转移时，枚举根节点 `k`，考虑将节点 `k` 作为根节点的贡献，递归计算左右子树的贡献，并加上节点 `i` 到 `j` 的权值和。