Recursive, Memoization, Tabulation Approach Java
Complexity\n- Time complexity: O(n^3) for tabulation\n\n- Space complexity: O(n^2)\n\n# Code\n\nclass Solution {\n    public int minScoreTriangulation(int[] val
# Complexity\n- Time complexity: $$O(n^3)$$ for tabulation\n\n- Space complexity: $$O(n^2)$$\n\n# Code\n```\nclass Solution {\n    public int minScoreTriangulation(int[] values) {\n        int n = values.length;\n        // return helperRec(values, 0, n - 1);\n\n        int[][] dp = new int[n + 1][n + 1];\n        for(int[] row : dp) Arrays.fill(row, -1);\n        return helperMem(values, 0, n - 1, dp);\n\n        // return helperTab(values);\n    }\n    \n    // RECURSIVE APPROACH\n    public int helperRec(int[] values, int i, int j){\n        if(i + 1 == j) return 0; // if there are only two nodes then a triangle cannot be obtained.\n        int ans = Integer.MAX_VALUE;\n        for(int k = i + 1; k < j; k++){\n            ans = Math.min(ans, values[i] * values[j] * values[k] + helperRec(values, i, k) + helperRec(values, k, j));\n        }\n        return ans;\n    }\n    // MEMOIZATION APPROACH\n    public int helperMem(int[] values, int i, int j, int[][] dp){\n        if(i + 1 == j) return 0; // if there are only two nodes then a triangle cannot be obtained.\n        if(dp[i][j] != -1) return dp[i][j];\n        int ans = Integer.MAX_VALUE;\n        for(int k = i + 1; k < j; k++){\n            ans = Math.min(ans, values[i] * values[j] * values[k] + helperMem(values, i, k, dp) + helperMem(values, k, j, dp));\n        }\n        return dp[i][j] = ans;\n    }\n    // TABULATION APPROACH\n    public int helperTab(int[] values){\n        int x = values.length;\n        int[][] dp = new int[x + 1][x + 1];\n\n        for(int i = x - 1; i >= 0; i--){\n            for(int j = i + 2; j < x; j++){ // i + 2 se isliye start kra h because minimum 3 nodes honi chaiye to 1 and 2 pe triangle nhi bnega\n                int ans = Integer.MAX_VALUE;\n                for(int k = i + 1; k < j; k++){\n                    ans = Math.min(ans, values[i] * values[j] * values[k] + dp[i][k] + dp[k][j]);\n                }\n                dp[i][j] = ans;\n            }\n        }\n        return dp[0][x - 1];\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Java']