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]; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter