Q27 Minimum Score Triangulation of Polygon - LeetCode 1039
Sat Mar 25 2023 14:08:26 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int minScoreTriangulation(int[] values) {
/* question no 27 in notes of dp playlist , catalan number , gap
strategy and matrix chain multiplication are being used
1) make 2d dp array to store results of previous polygon
2)every cell denotes minimum score to make that polygon with that
many sides
3) traversing the gap diagnols and handling trivial cases 0 , 1
4) handling further gap diagonals through formula for left , right
and immediate triangle using gap strategy 2
*/
int n = values.length;
int[][] dp = new int[n][n];
for(int gap = 0 ; gap < n ; gap ++){
for(int i = 0 , j = gap ; j < n ; i++ , j++){
if(gap == 0 )
dp[i][j] = 0;
else if(gap == 1)
dp[i][j] = 0;
//only 1 triangle can be formed with 3 points
else if(gap == 2)
dp[i][j] = values[i] * values[i+1] * values[i+2];
else{
//4
int min = Integer.MAX_VALUE;
for(int k = i+1 ; k<= j-1 ; k++){
int left = dp[i][k];
int right = dp[k][j];
int triangle = values[i] * values[j] * values[k];
min = Math.min(min , left + right + triangle);
}
dp[i][j] = min;
}
}
}
return dp[0][n-1];
}
}
content_copyCOPY
https://leetcode.com/problems/minimum-score-triangulation-of-polygon/
Comments