fork download 
  1. #include <vector>
  2. #include <iostream>
  3. #include <limits.h>
  4.  
  5. using namespace std;
  6.  
  7. int sum(vector<int> freq, int i, int j) {
  8.  
  9. 	int s = 0;
  10. 	for (int x = i; x <= j; x++) {
  11. 		s += freq[x];
  12. 	}
  13.  
  14. 	return s;
  15. }
  16.  
  17. int optimalSearchTree(vector<int> keys, vector<int> freq) {
  18.  
  19.  
  20. 	int n = keys.size();
  21. 	vector<vector<int>> cost(n, vector<int>(n, 0));
  22.  
  23. 	for (int i = 0; i < n; i++) {
  24. 		cost[i][i] = keys[i];
  25. 	}
  26.  
  27. 	for (int L = 2; L <= n; L++) {
  28.  
  29. 		for (int i = 0; i <= n - L + 1; i++) {
  30.  
  31. 			int j = i + L - 1;
  32. 			cost.at(i).at(j) = INT_MAX;
  33.  
  34. 			for (int r = i; r <= j; r++) {
  35.  
  36.  
  37. 				int c = ((r > i) ? cost[i][r - 1] : 0) +
  38. 					((r < j) ? cost[r + 1][j] : 0) +
  39. 					sum(freq, i, j);
  40.  
  41. 				if (c < cost[i][j]) {
  42. 					cost[i][j] = c;
  43. 				}
  44.  
  45. 			}
  46. 		}
  47. 	}
  48.  
  49. 	return cost[0][n - 1];
  50. }
  51.  
  52.  
  53. int main() {
  54.  
  55. 	vector<int> keys = { 10,12,16,21 };
  56. 	vector<int> freq = { 4,2,6,3 };
  57.  
  58. 	cout << optimalSearchTree(keys, freq) << endl;
  59.  
  60. }
  61.  
  62.  
  63.  
Runtime error #stdin #stdout #stderr 0s 3468KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 4) >= this->size() (which is 4)
https://ideone.com/oxNoRR
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!