最优二叉搜索树

void OptimalBinarySearchTree(int a, int b, int n, int** m, int** s, int** w) {
    for (int i = 1; i <= n; i++) {
        w[i + 1][i] = a[i];
        m[i + 1][i] = 0;
    }
    for (int r = 0; r < n; r++) {
        for (int i = 1; i <= n - r; i++) {
            int j = i + r;
            w[i][j] = w[i][j - 1] + a[j] + b[j];
            m[i][j] = m[i + 1][j];
            s[i][j] = i;
            for (int k = i + 1; k <= j; k++) {
                int t = m[i][k - 1] + m[k + 1][j];
                if (t < m[i][j]) {
                    m[i][j] = t;
                    s[i][j] = k;
                }
            }
            m[i][j] += w[i][j];
        }
    }
}

最后更新: 2024年1月2日 21:37:12
创建日期: 2024年1月2日 16:56:10
回到页面顶部