Tabulation || Dynamic Programming
This problem seeks knowledge of Matrix chain multiplication which uses 1 unique pattern of DP that is GAP Strategy, for visualising the problem you need to draw
This problem seeks knowledge of ***Matrix chain multiplication*** which uses 1 unique pattern of DP that is **GAP Strategy**, for visualising the problem you need to draw all the possible **triangulation** of given polygon, which will be easier if you know about ***catalan numbers*** and it\'s application.\nThen this solution will make sense.\n```\nclass Solution {\n    public int minScoreTriangulation(int[] values) {\n        int len = values.length;\n        int[][] dp = new int[len][len];\n        for(int gap = 2;gap<len;gap++){\n            \n            for(int i=0,j=gap;j<len;i++,j++){\n                if(gap==2) dp[i][j] = values[i]*values[i+1]*values[i+2];\n                else{\n                    int min = Integer.MAX_VALUE;\n                    for(int k=i+1;k<j;k++){\n                        int base = values[i]*values[j]*values[k];\n                        int above = dp[i][k];\n                        int down = dp[k][j];\n                        int total = base+above+down;\n                        if(total<min) min = total;\n                    }\n                    dp[i][j] = min;\n                }\n            }\n        }\n        return dp[0][len-1];\n    }\n}\n```\n\nHappy coding, this problem is very intutive and infuses lot of concept at a time, code is not hard but it\'s intution is hard to think,\nthere are problems in leetcode which counts as medium though their solution is above 100 lines of code, they are medium coz they are implementaion based, and this problem is intution based that\'s why it is hard to crack in first go.\nHappy coding\uD83D\uDE0A\uD83D\uDE4F
['Dynamic Programming', 'Java']