Climbing Stairs

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?

Notes:

  1. Coordinate DP
  2. Space optimization
    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }

        // state
        int[] f = new int[n];

        // initialize
        f[0] = 1;
        f[1] = 2;

        // function
        for (int i = 2; i < n; ++i) {
            f[i] = f[i-1] + f[i-2];
        }

        // answer
        return f[n-1];
    }

    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }

        int lastLast = 1;
        int last = 2;

        // function
        int current = 2;
        for (int i = 2; i < n; ++i) {
            current = last + lastLast;
            lastLast = last;
            last = current;
        }

        // answer
        return current;
    }

results matching ""

    No results matching ""