Skip to content

Instantly share code, notes, and snippets.

@jason810496

jason810496/OptimalBinarySearchTree

Last active May 20, 2024 07:40
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jason810496/f2257cec61b2d698b1b2e9386ed0731c to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jason810496/f2257cec61b2d698b1b2e9386ed0731c to your computer and use it in GitHub Desktop.
Download ZIP
Raw
README.md 
g++ -std=c++11 OptimalBinarySearchTree.cpp
./a.out > OptimalBinarySearchTree
Raw
OptimalBinarySearchTree
Optimal BST Cost: 31
e:(expected cost)
+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+
| 0 | 2 | 9 | 21| 31|
+---+---+---+---+---+
| 0 | 0 | 3 | 14| 21|
+---+---+---+---+---+
| 0 | 0 | 0 | 4 | 11|
+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 2 |
+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+
w:(weight, prefix sum of p and q)
+---+---+---+---+---+
| 3 | 10| 15| 23| 28|
+---+---+---+---+---+
| 0 | 2 | 7 | 15| 20|
+---+---+---+---+---+
| 0 | 0 | 3 | 11| 16|
+---+---+---+---+---+
| 0 | 0 | 0 | 4 | 9 |
+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 2 |
+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+
root:
+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+
| 0 | 1 | 2 | 2 | 3 |
+---+---+---+---+---+
| 0 | 0 | 2 | 3 | 3 |
+---+---+---+---+---+
| 0 | 0 | 0 | 3 | 3 |
+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 4 |
+---+---+---+---+---+
Raw
OptimalBinarySearchTree.cpp
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define ll long long
#define OAO cin.tie(0);ios_base::sync_with_stdio(0);
#define F first
#define S second
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef vector< pair<int,int> > vpii;
const int MAX_N = 1e5;
const int INF = 1e9;
const int MOD = 1e9+7;
/* optimal binary search tree */
void print_table(vvi &vec){
cout<<"+";
for(int i=0;i<vec[0].size();i++) cout<<"---+";
cout<<"\n";
for(int i=0;i<vec.size();i++){
cout<<"| ";
for(int j=0;j<vec[i].size();j++){
cout<<vec[i][j];
if( j!=vec[i].size()-1 && vec[i][j+1] > 9 && vec[i][j] <= 9 ){
cout<<" | ";
}
else if(vec[i][j] > 9){
cout<<"| ";
}
else{
cout<<" | ";
}
}
cout<<"\n";
cout<<"+";
for(int i=0;i<vec[0].size();i++) cout<<"---+";
cout<<"\n";
}
}
int optimal_bst_top_down(int l, int r, vi &p, vvi &dp ,vvi &w, vvi &root){
if(l>r) return 0;
if(l==r){
root[l][r] = l;
dp[l][r] = w[l][r];
}
if(dp[l][r]!=0) return dp[l][r];
int ans = INF;
for(int i=l;i<=r;i++){
int temp = optimal_bst_top_down(l,i-1,p,dp,w,root) + optimal_bst_top_down(i+1,r,p,dp,w,root) + w[l][r];
if(temp < ans){
ans = temp;
root[l][r] = i;
}
}
return dp[l][r] = ans;
}
signed main(){
OAO
int n=4;
vector<int> key { 0, 1, 2, 3, 4 };
vector<int> p = { 0, 5, 2, 4, 3 }; // frequency to access key[i]
vector<int> q = { 3, 2, 3, 4, 2 }; // failure to access key[i]
vector<vi> e(n+2, vi(n+1,0)); // expected cost
vector<vi> w(n+2, vi(n+1,0)); // weight ( prefix sum of p and q)
vi prefix_p(n+1,0);
vi prefix_q(n+1,0);
vector<vi> root(n+1, vi(n+1,0));
// pre compute weight
prefix_p[0] = p[0];
prefix_q[0] = q[0];
for(int i=1;i<=n;i++){
prefix_p[i] = prefix_p[i-1] + p[i];
prefix_q[i] = prefix_q[i-1] + q[i];
}
for(int i=0;i<=n;i++){
for(int j=i;j<=n;j++){
// w[i][j] =
// p[ i+1 .. j ]
// q[ i .. j ]
w[i][j] = ( prefix_p[j]-prefix_p[i] ) + (prefix_q[j]-prefix_q[i-1]);
}
}
cout<<"Optimal BST Cost: "<<optimal_bst_top_down(1,n,p,e,w,root)<<"\n";
cout<<"e:(expected cost)\n";
print_table(e);
cout<<"w:(weight, prefix sum of p and q)\n";
print_table(w);
cout<<"root:\n";
print_table(root);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment