首页 > 代码库 > LeetCode Climbing Stairs 爬楼梯
LeetCode Climbing Stairs 爬楼梯
递归法（TLE代码）：
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 if(n==0) 5 return 1; 6 if(n<0) 7 return 0; 8 return (climbStairs(n-1)+climbStairs(n-2)); 9 }10 };
动态规划法：
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 if(n==1) return 1; 5 if(n==2) return 2; 6 int a=1,b=2,c=0,i; 7 for( i=0;i<n-2 ;i++ ){ 8 c=a+b; 9 a=b;10 b=c;11 }12 return c;13 }14 };
题意：爬楼梯，给出一条楼梯的阶数，每次可以走1步，或者两步一起走，那么就有两种走法走完这n阶。问有多少种走法走完这楼梯，返回它。
思路：当n=1时，返回1；当n=2时，返回2。当n>3时，要返回的是n-1和n-2所要返回的数。比如n=3，那么就返回1+2的值，n=4，返回3+2。类推下去。
吐槽：原来很困惑这个问题，用递归写了一下，发现不行，虽然代码很简单。之后考虑各种方法，再用此递归法计算一下各个返回值，发现了规律，原来如此。~
LeetCode Climbing Stairs 爬楼梯
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。