Recursive Triangulation with Dynamic Programming
Intuition\nWe have to recursively form every possible triangles \n\n# Approach\nWe select first index and last index as a base, and the function recursively fin
# Intuition\nWe have to recursively form every possible triangles \n\n# Approach\nWe select first index and last index as a base, and the function recursively find the best possible third index\n\n# Complexity\n-Time complexity:\nO(n^3)\n\n-Space complexity:\nO(n^2) + O(n)\n\n# Recursive and Memoized Code \n```\nclass Solution {\n    int f(vector<int> &nums, int i, int j, vector<vector<int>> &dp) {\n        //if there is no vertex in between \'i\' and \'j\' \n        //then no triangles will be formed between them\n        if(i + 1 == j)\n            return 0;\n        \n        if(dp[i][j] != -1)\n            return dp[i][j];\n        \n        int mini = INT_MAX;\n        //searching for \'k\' between \'i\' and \'j\'\n        //so traversing from (i+1) to (j-1)\n        for(int k=i+1; k<j; k++) {\n            //recursively taking \'i\' and \'k\' as one base and fining third vertex between them\n            //similar recursive call for \'k\' and \'j\'\n            int score = (nums[i] * nums[j] * nums[k]) + f(nums, i, k, dp) + f(nums, k, j, dp);\n            mini = min(mini, score);\n        }\n        return dp[i][j] = mini;\n    }\npublic:\n    int minScoreTriangulation(vector<int>& nums) {\n        int n = nums.size();\n        vector<vector<int>> dp(n+1, vector<int>(n+1, -1));\n        \n        //selecting the first vertex and last vertex as base and searching for third vertex\n        return f(nums, 0, n-1, dp);\n\n    }\n};\n```\n# Tabulated Code\n```\nclass Solution {\npublic:\n    int minScoreTriangulation(vector<int>& nums) {\n        int n = nums.size();\n        vector<vector<int>> dp(n+1, vector<int>(n+1, 0));\n        \n        for(int i=n-1; i>=0; i--) {\n            //j starts from (i+2) because there should be atleast one \n            //vertex between them to form a traingle and\n            //and that\'s why k starts from (i+1) till (j-1)\n            for(int j=i+2; j<n; j++) {\n                int mini = INT_MAX;\n                for(int k=i+1; k<j; k++) {\n                    int score = (nums[i] * nums[j] * nums[k]) + dp[i][k] + dp[k][j];\n                    mini = min(mini, score);\n                }\n                dp[i][j] = mini;\n            }\n        }\n        \n        return dp[0][n-1];\n\n    }\n};\n\n```\n\n
['Divide and Conquer', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++']