70 climbing stairs

---

title: Climbing Stairs
tags:
- climbing-stairs
- No.70
- simple
- combination
- pascal-triangle
- fibonacci

---

Problem

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Corner Cases

Solutions

Naive Combination

Suppose x 2-steps and y 1-steps. Then n = y + 2x. If we have x + y boxes:

[1], [2], ..., [x + y -1], [x + y]

x boxes are randomly choosen as 2-steps or y are choosen as 1-steps, then all situations are \binom{x + y}{x} = \binom{x + y}{y}. In another word, the number to be figured out is:

\sum_{x, y} \binom{x + y}{x} = \sum_{x=0}^{2x \leq n} \binom{n - x}{x}

that is

\binom{n}{0} + \binom{n - 1}{1} + \binom{n - 2}{2} + \cdots

There are two ways to compute any combination number:

1. By definition
2. By Pascal's Triangle

By defintion, we compute \binom{x + y}{x} = \frac{(x + y)!}{x!y!}. This is fast, but also dangerous for int. Since factorial grows so fast, a! would be greater than 2147483647 very soon. The running time is O(n^2).

By Pascal's Triangle,

        1   1
      1   2   1
    1   3   3   1
  1   4   6   4   1
1   5  10  10   5   1

we have the relationship:

\binom{m}{n} = \binom{m-1}{n-1} + \binom{m}{n-1}

This recurrence formula avoids the computation of factorial, but is quite slow.

class Solution {
    public int climbStairs(int n) {
        int x = 0;
        int s = 0;
        while (2 * x <= n) {
            s = s + combination1(n - x, x);
            x = x + 1;
        }
        return s;
    }

    private int combination1(int a, int b) {
        int c1 = 1;
        int c2 = 1;
        for (int i=1; i<=a-b; i++) {
            c1 = c1 * (i + b);
            c2 = c2 * i;
        }
        return c1 / c2;
    }

    private int combination2(int a, int b) {        
        if (b == 0 || b == a) {return 1;}
        return combination(a - 1, b - 1) + combination(a - 1, b);
    }
}

Improved Pascal's Triangle

We can use an array int[2][n+1] binom to record the combination numbers to avoid too much recurrences.

The running time is O(n^2).

class Solution {
    public int climbStairs(int n) {
        int[][] binom = new int[2][n+1];
        int     s     = 0;
        for (int i=1; i<=n; i++) {
            for (int j=0; j<=i; j++) {
                binom[i%2][j] = (j == 0 || j == i) ? 1 : binom[1-i%2][j-1] + binom[1-i%2][j];
                s = (i + j == n) ? s + binom[i%2][j] : s;
            }
        }
        return s;
    }
}

Fibonacci

If climbing-stairs number for input n is f(n), then for f(n+1):

1. Climb one 2-step from f(n-1).
2. Climb two 1-step from f(n).

Thus f(n+1) = f(n) + f(n-1). For beginning condition, f(1)=1, f(2)=2, f(3)=3, it's obvious that sequence \{f(n)\} is Fibonacci Sequence.

Note that from the induction above, we have achieved a combinatorial method to compute Fibonacci number:

f(n) = \sum_{x=0}^{2x \leq n} \binom{n-x}{x} = \binom{n}{0} + \binom{n - 1}{1} + \binom{n - 2}{2} + \cdots

If we do recurrence f(n+1) = f(n) + f(n-1), then it's very slow since there are so many duplicated terms:

f(5) =  f(4) + f(3)
     =  f(3) + f(2)
      + f(2) + f(1)
     =  f(2) + f(1) + f(1) + f(1)
      + f(1) + f(1) + f(1)
     =  f(1) + f(1) + f(1) + f(1) + f(1)
      + f(1) + f(1) + f(1)

While the computation in sequence has naturally recorded the duplicated terms. Thus running time is O(n):

class Solution {
    public int climbStairs(int n) {
        int a = 0;
        int b = 1;
        int f = 0;
        
        for (int i=0; i<n; i++) {
            f = a + b;
            a = b;
            b = f;
        }
        return f;
    }
}