LeetCode 1039 Minimum Score Triangulation of Polygon - Implementation

Base case: $dp[i][i+1] = 0$ (an edge is not a polygon, no triangulation needed). Iterate by polygon size (number of vertices in the sub-polygon). For each interval $[i, j]$ where $j - i \geq 2$, try all intermediate vertices $k$. Time: $O(n^3)$, Space: $O(n^2)$. Same complexity as Matrix Chain Multiplication. The base case is edges (two adjacent vertices), which need no triangulation. Build up from there.

Time complexity: $O(n^3)$.

Space complexity: $O(n^2)$.