Climbing Stairs

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

递归法

说明

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

复杂度

时间O(n) 空间O(n)

代码

public int climbStairs(int n) {    int[] dp = new int[n + 1];    dp[0] = 1;    dp[1] = 1;    for (int i = 2; i <= n; i++) {        dp[i] = dp[i - 1] + dp[i - 2];    }    return dp[n];    }

复杂度

时间O(n) 空间O(1)

代码

public int climbStairs(int n) {

    int[] res = new int[3];    res[0] = 0;    res[1] = 1;    res[2] = 2;    if (n < 3) {        return res[n];    }    for (int i = 3; i <= n; i++) {        res[0] = res[1];        res[1] = res[2];        res[2] = res[1] + res[0];    }    return res[2];    }