Basic Problemscountingcombinatorics

Ways to Triangulate a Polygon

Given a convex polygon with n vertices, count the number of ways to split its interior into triangles using diagonals that never cross each other.

Do this lesson first: climbing stairs

Example input

n = 5 (a convex pentagon)

Expected output

5

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[v] = sum over apex k from 2 to v - 1 of dp[k] × dp[v - k + 1]

Fix one edge, from corner 1 to corner v. In any triangulation that edge belongs to exactly one triangle, and its third corner, the apex k, is one of corners 2 to v - 1. That triangle cuts the rest into the polygon on corners 1 to k (k corners) and the polygon on corners k to v (v - k + 1 corners), triangulated independently, so for one apex the counts multiply. Every triangulation has exactly one triangle on the fixed edge, so each is counted under exactly one apex, and the apexes are added. It is a sum over the apex, never a pick of the best one. Matrix chain multiplication, in the interval family, loops over a middle split the same way and takes a min instead.

dp[2] = 1 is the base, and it is the odd one: a polygon with two corners is a single edge, and there is exactly one way to triangulate it, by doing nothing. It is there so that an apex next to the fixed edge (k = 2 or k = v - 1), which leaves only an edge on one side, multiplies by 1 instead of needing a special case. dp[3] = dp[2] × dp[2] = 1 then falls out of the recurrence: a triangle is already triangulated. Every cell reads only smaller corner counts, so left to right works.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[2] = 1 is the base, and it is the odd one: a polygon with two corners is a single edge, and there is exactly one way to triangulate it, by doing nothing. It is there so that an apex next to the fixed edge (k = 2 or k = v - 1), which leaves only an edge on one side, multiplies by 1 instead of needing a special case. dp[3] = dp[2] × dp[2] = 1 then falls out of the recurrence: a triangle is already triangulated. Every cell reads only smaller corner counts, so left to right works.

i=2

i=3

i=4

i=5

i=6

1

2

5

14

ways-to-triangulate-a-polygon.ts

1function triangulations(n) {
2 const dp = new Array(n + 1).fill(0);
3 dp[2] = 1;
4 for (let v = 3; v <= n; v++) {
5 for (let k = 2; k < v; k++) {
6 dp[v] += dp[k] * dp[v - k + 1];
7 }
8 }
9 return dp[n];
10}

Base caseComputedBeing readAnswer

The code, the trap, the variations

ways-to-triangulate-a-polygon.ts

1function triangulations(n) {
2 const dp = new Array(n + 1).fill(0);
3 dp[2] = 1;
4 for (let v = 3; v <= n; v++) {
5 for (let k = 2; k < v; k++) {
6 dp[v] += dp[k] * dp[v - k + 1];
7 }
8 }
9 return dp[n];
10}

Where people go wrong

Indexing off by two. A polygon with v corners has C(v - 2) triangulations, not C(v), so reusing a Catalan table indexed by corner count reports 132 for the hexagon instead of 14. The shift comes from the base: this recurrence bottoms out at a two-corner edge, not at a zero-corner polygon.

Give each triangle a cost, such as the product of its corner values, and minimise the total.
Same fixed edge and same loop over the apex, but the two sides are no longer multiplied: each apex costs the left side plus the right side plus its own triangle, and the apexes are compared by min. The cost depends on which corners a side spans, so the state becomes the range of corners from i to j.
Count dissections into any convex pieces, not only triangles, still with non-crossing diagonals.
The piece on the fixed edge may now have any number of corners, so the split runs over a set of corners instead of one apex, and the numbers change: 1, 3, 11, 45 for 3 to 6 corners, counting the undivided polygon as one dissection. The fixed edge, and multiplying the counts of the independent regions either side, stay.

Count Valid Parenthesis Min Sum in a Triangle