Basic Problemscountingcombinatorics

nth Catalan Number

Return the nth Catalan number, a count that shows up whenever you tally balanced arrangements such as valid bracket sequences of a given length. The first few values run 1, 1, 2, 5, 14.

Do this lesson first: climbing stairs

Example input

n = 5

Expected output

42

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[i] = sum over k from 0 to i - 1 of dp[k] × dp[i - 1 - k]

Ask which multiplication happens last. In a fully bracketed product exactly one multiplication sits outermost, and it joins a left block to a right block. If the left block uses k multiplications, the right block uses the other i - 1 - k. The two blocks are bracketed independently, so for one value of k the counts multiply: dp[k] × dp[i - 1 - k]. Different values of k put the outermost multiplication in different places, so no bracketing is counted twice, and the values of k are added. Every split is added and none is compared, because this is a count and every split contributes. Matrix chain multiplication, in the interval family, runs this same loop over the last multiplication but keeps only the cheapest split, so it takes a min instead of a sum.

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[0] = 1: a single factor needs no multiplication, and there is exactly one way to leave it alone, so it is 1 (it is a factor in a product, never a term on its own). dp[1] is not a base: it falls out of the recurrence as dp[0] × dp[0] = 1. Every cell reads only smaller indices, so filling left to right means everything it needs is already written.

i=0

i=1

i=2

i=3

i=4

i=5

1

2

5

14

42

nth-catalan-number.ts

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

Base caseComputedBeing readAnswer

The code, the trap, the variations

nth-catalan-number.ts

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

Where people go wrong

Storing the table in 32-bit integers. C(19) = 1,767,263,190 still fits, C(20) = 6,564,120,420 does not, and in Java or C++ the overflow is silent: the loop keeps filling cells with wrong numbers and nothing fails. JavaScript numbers stay exact up to C(30), which hides the bug until the same code is ported or n grows.

Use the closed form C(2n, n) / (n + 1) instead of a table.
The same number in O(n) time with no table, provided the arithmetic is exact: the intermediate C(2n, n) is n + 1 times the answer, so fixed-width integers overflow on it sooner than on the table. Nothing of the split argument survives either. The table is the version that still works once the splits gain weights or restrictions, as in the next variation.
Give every split a cost and ask for the cheapest bracketing: matrix chain multiplication.
The loop over the last multiplication stays and the sum becomes a min. The state must also say WHICH factors a block holds, an interval from i to j, rather than how many, because a split's cost depends on the dimensions of the factors either side. That is the interval2d family.
Return the answer for large n, modulo 1e9 + 7.
Every product and every running sum gains a modulo; the loop and the order do not change. In JavaScript the product of two residues can pass 2^53, so that multiplication needs BigInt or a mulmod helper. Without any modulo, JavaScript numbers stop being exact at C(31) and a signed 64-bit integer first overflows at C(36).

Maximum Segments Count Unique BSTs