[Java/C++/Python] DP
Intuition\n\nThe connected two points in polygon shares one common edge,\nthese two points must be one and only one triangles.\n\n\n\n## Explanation\n\ndp[i][j]
## **Intuition**\n\nThe connected two points in polygon shares one common edge,\nthese two points must be one and only one triangles.\n\n<br>\n\n## **Explanation**\n\n`dp[i][j]` means the minimum score to triangulate `A[i] ~ A[j]`,\nwhile there is edge connect `A[i]` and `A[j]`.\n\nWe enumerate all points `A[k]` with `i < k < j` to form a triangle.\n\nThe score of this triangulation is `dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[j] * A[k]`\n\n<br>\n\n**Java, bottom-up:**\n```\n    public int minScoreTriangulation(int[] A) {\n        int n = A.length;\n        int[][] dp = new int[n][n];\n        for (int d = 2; d < n; ++d) {\n            for (int i = 0; i + d < n; ++i) {\n                int j = i + d;\n                dp[i][j] = Integer.MAX_VALUE;\n                for (int k = i + 1; k < j; ++k)\n                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[j] * A[k]);\n            }\n        }\n        return dp[0][n - 1];\n    }\n```\n\n**Java, bottom-up, another loop version**\n```\n    public int minScoreTriangulation(int[] A) {\n        int n = A.length;\n        int[][] dp = new int[n][n];\n        for (int j = 2; j < n; ++j) {\n            for (int i = j - 2; i >= 0; --i) {\n                dp[i][j] = Integer.MAX_VALUE;\n                for (int k = i + 1; k < j; ++k)\n                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[j] * A[k]);\n            }\n        }\n        return dp[0][n - 1];\n    }\n```\n\n**C++, bottom-up:**\n```\n    int minScoreTriangulation(vector<int>& A) {\n        int n = A.size();\n        vector<vector<int>> dp(n, vector<int>(n));\n        for (int j = 2; j < n; ++j) {\n            for (int i = j - 2; i >= 0; --i) {\n                dp[i][j] = INT_MAX;\n                for (int k = i + 1; k < j; ++k)\n                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[j] * A[k]);\n            }\n        }\n        return dp[0][n - 1];\n    }\n```\n\n**Python, bottom-up**\n```\n    def minScoreTriangulation(self, A):\n        n = len(A)\n        dp = [[0] * n for i in xrange(n)]\n        for d in xrange(2, n):\n            for i in xrange(n - d):\n                j = i + d\n                dp[i][j] = min(dp[i][k] + dp[k][j] + A[i] * A[j] * A[k] for k in xrange(i + 1, j))\n        return dp[0][n - 1]\n```\n\n**Python, top-down:**\n```\n    def minScoreTriangulation(self, A):\n        memo = {}\n        def dp(i, j):\n            if (i, j) not in memo:\n                memo[i, j] = min([dp(i, k) + dp(k, j) + A[i] * A[j] * A[k] for k in range(i + 1, j)] or [0])\n            return memo[i, j]\n        return dp(0, len(A) - 1)\n```\n\n
[]