算法导论 ch15 动态规划 最优二叉查找树

1. source code

#include <iostream>
using namespace std;
void optimalBST(double *p, double *q, int n) {
	const int COL = n + 2;
	double *e = new double[(n + 2) * COL];
	double *w = new double[(n + 2) * COL];
	int *root = new int[(n + 2) * COL];
	for (int i = 1; i <= n + 1; i++) {
		e[i * COL + (i - 1)] = q[i - 1];
		w[i * COL + (i - 1)] = q[i - 1];
	}
	for (int l = 1; l <= n; l++) {
		for (int i = 1; i <= n - l + 1; i++) {
			int j = i + l - 1;
			e[i * COL + j] = numeric_limits<int>::max();
			w[i * COL + j] = w[i * COL + j - 1] + p[j]+ q[j];
			for (int r = i ; r <= j; r++) {
				double t = e[i * COL + r - 1] + e[(r + 1) * COL + j]+ w[i * COL + j];
				if (t < e[i * COL + j]) {
					e[i * COL + j] = t;
					root[i * COL + j] = r;
				}
			}
		}
	}
	cout << "matrix e :"<< endl;
	for (int i = 1; i < COL; i++) {
		for (int j = 0; j <= n; j++) {
			cout << e[i * COL + j]<< " ";
		}
		cout << endl;
	}
	cout << "matrix w :"<< endl;
	for (int i = 1; i < COL; i++) {
		for (int j = 0; j <= n; j++) {
			cout << w[i * COL + j]<< " ";
		}
		cout << endl;
	}
	cout << "matrix root :"<< endl;
	for (int i = 1; i < COL - 1; i++) {
		for (int j = 1; j < COL - 1; j++) {
			cout << root[i * COL + j]<< " ";
		}
		cout << endl;
	}
}
int main() {
	double p[] = { 0, 0.15, 0.1, 0.05, 0.1, 0.2 };
	double q[] = { 0.05, 0.1, 0.05, 0.05, 0.05, 0.1 };
	int n = sizeof(p)/sizeof(double);
	optimalBST(p, q, n - 1);
}

2. test result

matrix e :
0.05 0.45 0.9 1.25 1.75 2.75 
0 0.1 0.4 0.7 1.2 2 
0 0 0.05 0.25 0.6 1.3 
0 0 0 0.05 0.3 0.9 
0 0 0 0 0.05 0.5 
0 0 0 0 0 0.1 
matrix w :
0.05 0.3 0.45 0.55 0.7 1 
0 0.1 0.25 0.35 0.5 0.8 
0 0 0.05 0.15 0.3 0.6 
0 0 0 0.05 0.2 0.5 
0 0 0 0 0.05 0.35 
0 0 0 0 0 0.1 
matrix root :
1 1 2 2 4 
0 2 2 2 4 
0 0 3 4 5 
0 0 0 4 5 
0 0 0 0 5