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 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
class Solution { public: int climbStairs(int n) { int *a = new int [n + 1]; a[0] = 1; a[1] = 1; for(int i = 2; i <= n; i++) { a[i] = a[i - 1] + a[i - 2]; } return a[n]; } }; //一开始我写了个Fibonacci递归，在n = 44 时候超时了 class Solution { public: int climbStairs(int n) { if(n == 1 || n == 2) return n; return climbStairs(n - 1) + climbStairs(n - 2); } }; //最最一开始我用的最原始的递归， 在 n=38的时候超时了 class Solution { public: int ans = 0; int climbStairs(int n) { if(n == 0) { ans++; return ans; } if(n >= 1) { climbStairs(n - 1); } if(n >= 2) { climbStairs(n - 2); } } }; |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
