Pascal's Triangle

Each row of Pascal's triangle starts and ends with 1, and every inner value is the sum of the two values above it:

        1
       1 1
      1 2 1
     1 3 3 1

Row n, entry k equals C(n, k), so the triangle is a nCr lookup table you can build with additions alone, with no division or overflow worries.

Build each row from the previous one: this "row i depends only on row i−1" structure is the essence of tabulated dynamic programming.