-
Notifications
You must be signed in to change notification settings - Fork 0
/
minSroreTriangulationOfPolygon.cpp
71 lines (54 loc) · 2.21 KB
/
minSroreTriangulationOfPolygon.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public:
int solveRec(vector<int>&values , int i ,int j){
// base case
if(i+1 == j) // can't make triangle from 2 points
return 0;
int ans = INT_MAX;
for(int k = i+1 ;k<j;k++){ // to run for 3rd point from next to last
// recursion relation
ans = min(ans ,values[i]*values[j]*values[k] + solveRec(values , i ,k) +solveRec(values ,k , j) );
}
return ans;
}
//Top Down Approach
int solveMem(vector<int>&values , int i ,int j , vector<vector<int>>&dp){
// base case
if(i+1 == j) // can't make triangle from 2 points
return 0;
if(dp[i][j] != -1) // alredy exist then simply return
return dp[i][j];
int ans = INT_MAX;
for(int k = i+1 ;k<j;k++){ // to run for 3rd point from next to last
// recursion relation
ans = min(ans ,values[i]*values[j]*values[k] + solveMem(values , i ,k,dp) +solveMem(values ,k , j,dp) );
}
dp[i][j] = ans;
return dp[i][j];
}
// Bottom Up Approach
int solveTab(vector<int>&values ){
int n = values.size();
vector<vector<int>>dp(n, vector<int>(n+1, 0));
for(int i = n-1 ;i>=0;i--){
for(int j = i+2 ;j < n;j++){ // i+2, for atleat 3 points is reqiured for triangle
int ans = INT_MAX;
for(int k = i+1 ;k<j;k++){
// recursion relation
ans = min(ans ,values[i]*values[j]*values[k] + dp[i][k] + dp[k][j]);
}
dp[i][j] = ans;
}
}
return dp[0][n-1];
}
int minScoreTriangulation(vector<int>& values) {
// int n = values.size();
// return solveRec(values , 0 , n-1); // FOR RECUSION ONLY
// int n = values.size();
// vector<vector<int>> dp(n, vector<int>(n+1 ,-1)); // RECURSION + MEMORIZATION
// return solveMem(values , 0 , n-1 , dp);
int n = values.size();
return solveTab(values);
}
};