LeetCode 70. Climbing Stairs

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?

?

一開始想用排列組合的方式，但是公式不太好些，后來想用遞歸的方式，最后剩一個臺階1種，最后剩2個臺階兩種，然后那個臺階相當于n-1個臺階的方法總數加上n－2個臺階的方法總數，但是這樣會超時。

最后用循環代替遞歸，臺階數不要倒著來，一個臺階一種，二個臺階2種，三個臺階種類數時一個臺階種類數加兩個臺階種類數以此類推。

class Solution {
public:int climbStairs(int n) {//最后一步可以是一階或者兩階，上一個臺階只有一種走法，兩個臺階兩種走法,遞歸會超時vector<int> waysOfNSteps(n);if(n == 1){return 1;}else if(n == 2){return 2;}else{waysOfNSteps[0] = 1;waysOfNSteps[1] = 2;for(int i = 2 ;i<n;i++ ){waysOfNSteps[i] = waysOfNSteps[i-1]+waysOfNSteps[i-2];}}return waysOfNSteps[n-1];}
};

?