Climbing Stairs

https://leetcode.com/problems/climbing-stairs/description/

Easy 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?

Thoughts

问有多少种想到DP. 和上题类似，到达i阶分别有从i - 1和i - 2两种方法， 因此设f(i)为在i阶的方法数，递推式f[i] = f[i - 1] + f[i - 2], 也就是斐波那契数列。

给定N,

设Fi为从0处往上爬一步或两步到i处的unique path的数目. 求F(N).

Code

class Solution {
    public int climbStairs(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        int[] f = new int[n];
        f[0] = 1;
        f[1] = 2;

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

        return f[n - 1];
    }
}

Analysis

做题耗时: 4min

时间复杂度为O(n), 空间复杂度也是O(n). 但我们观察到f[i]实际上只有i-1和i-2有关，完全不需要存整个数组。

Ver.2

class Solution {
    public int climbStairs(int n) {
        int[] f = new int[2];
        f[0] = 2; f[1] = 1;

        for (int i = 3; i <= n; i++) {
            f[i % 2] = f[(i - 1) % 2] + f[(i - 2) % 2];
        }
        return f[n % 2];
    }
}

Analysis

TC: O(n), SC: O(1)