Climbing Stairs leetcode

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?
时间复杂度为O(n)

• state: f[i] 表示爬到第i个楼梯的所有方法的和
• function： f[i] = f[i-1] + f[i-2] //因为每次走一步或者两步， 所以f[i]的方法就是它一步前和两步前方法加和
• initial： f[0] = 0; f[1] = 1; f[2] = 2
• end : return f[n]

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        if (n == 0 || n == 1 || n == 2){
            return n;
        }
        int [] sum = new int [n + 1];
        sum[1] = 1;
        sum[2] = 2;
        for (int i =3; i <= n; i++) {
            sum[i] = sum[i-1] + sum[i-2];
        }
        return sum[n];
    }
}
//O(1) 空间方法
public class Solution {
    public int climbStairs(int n) {
        if (n == 0 || n == 1 || n == 2){
            return n;
        }
        int [] sum = new int [3];
        sum[1] = 1;
        sum[2] = 2;
        for (int i =3; i <= n; i++) {
            sum[i%3] = sum[(i-1)%3] + sum[(i-2)%3];
        }
        return sum[n%3];
    }
}