70.|70. Climbing Stairs 70.ClimbingStairs

题目分析
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?
Note: Given n will be a positive integer.
Example 1:

Input: 2 Output:2 Explanation:There are two ways to climb to the top.1. 1 step + 1 step 2. 2 steps

【70.|70. Climbing Stairs】Example 2:

Input: 3 Output:3 Explanation:There are three ways to climb to the top.1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step

代码一
时间复杂度为O(2^n)，Time Limit Exceeded。

class Solution { public int climbStairs(int n) { if(n <= 2) { return n; } return climbStairs(n - 2) + climbStairs(n - 1); } }

代码二
动态规划的解法

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

代码三

class Solution { public int climbStairs(int n) { if (n == 1) return 1; int t1 = 1, t2 = 1, res = 0; for(int i = 2; i <= n; i++) { res = t1 + t2; t2 = t1; t1 = res; } return res; } }