C++ bottom up and memoization solution with explanation
\n/*\n   /*\n    https://leetcode.com/problems/minimum-score-triangulation-of-polygon/submissions/\n    \n    The idea is to  take each pair of vertices possibl
```\n/*\n   /*\n    https://leetcode.com/problems/minimum-score-triangulation-of-polygon/submissions/\n    \n    The idea is to  take each pair of vertices possible and then with those fixed, find \n    a vertex in between such that the polygon on left and right side of it are of min score.\n    \n*/\n\nclass Solution {\npublic:\n    // TC: O(N^3)\n    // SC: O(N^2)\n    int minScoreTriangulationTabular(vector<int>& arr) {\n        if(arr.empty())\n            return 0;\n        \n        const int N = arr.size();\n        // dp(i, j): min triangulation score of polygon with vertices \n        // starting from i..j and there is an edge between i and j\n        vector<vector<int> > dp(N, vector<int>(N, 0));\n        \n        // start swiping each vertex using index \'i\' and use the index\n        // \'j\' to keep the other end fixed, this i and j edge will then be evaluated\n        // with every other vertex in between them by making a triangle with it and checking\n        // the score of left and right side of remaining polygon.\n        // first vertex\n        for(int i = 2; i < N; i++) {\n            // second vertex\n            for(int j = i - 2; j >= 0; j--) {\n                // pick the third vertex in between the endpoints\n                for(int k = j + 1; k < i; k++) {\n                    int curr_area = arr[i] * arr[k] * arr[j]; \n                    dp[j][i] = min(dp[j][i] == 0 ? INT_MAX : dp[j][i],\n                                   dp[j][k] + curr_area + dp[k][i]);\n                }\n            }\n        }\n        return dp[0][N-1];\n    }\n    \n    // using memoization\n    // TC: O(N ^ 3)\n    // SC: O(N ^ 2)\n    int minScoreTriangulationRec(vector<vector<int> >& dp, \n                                 vector<int>& arr, int i, int j) {\n            \n        if(dp[i][j] == 0)\n            // pick a vertex in between and evaulate the triangulation score\n            for(int k = i + 1; k < j; k++) {\n                int curr_score = arr[i] * arr[k] * arr[j];\n                \n                dp[i][j] = min(dp[i][j] == 0 ? INT_MAX : dp[i][j],\n                              minScoreTriangulationRec(dp, arr, i, k) + // left polygon\n                              curr_score +  // curret triangle with (i, k, j) vertices\n                              minScoreTriangulationRec(dp, arr, k, j)); // right polygon\n            }    \n        \n        return dp[i][j];\n    }\n    \n    int minScoreTriangulationRecDriver(vector<int>& arr) {\n        if(arr.empty())\n            return 0;\n        const int N = arr.size();\n        vector<vector<int> > dp(N, vector<int>(N, 0));\n        \n        return minScoreTriangulationRec(dp, arr, 0, N-1);    \n    }\n    \n    int minScoreTriangulation(vector<int>& A) {\n        //return minScoreTriangulationTabular(A);\n        return minScoreTriangulationRecDriver(A);\n    }\n};\n```
[]