LeetCode: Climbing Stairs

Way 1: iteration
Too slow, cannot pass leetcode test for time limit exceeded.

1 2 3 4 5 6 7 8

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

Way 2: Dynamic programming

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public: int climbStairs(int n) { vector<int> record(n+1); //record.push_back(1); //record.push_back(1); record[0]=1; record[1]=1; for(int i=2;i<=n;i++){ record[i]=record[i-1]+record[i-2]; } return record[n]; } };

Here is a tip: when set the size of vector when initialization,  values added by push_back() will be put after the size. 

e.g.

1 2 3 4 5 6 7

int main(int argc, char *argv[]) { vector<int> v(3); v.push_back(1); for(int i=0;i<v.size();i++){ cout<<v[i]<<" "; } }

The output is: 0 0 0 1