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]; }