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] = 1end : 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) { 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];}