C++实现 LeetCode-70. Climbing Stairs

概述本文章向大家介绍C++实现 LeetCode-70. Climbing Stairs，主要包括C++实现 LeetCode-70. Climbing Stairs使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

方法一：递归（缺点：Time limit Exceeded）

思路：同fibonacci算法，典型的动态规划问题。

1.定义子问题：vec[i]表示跳到第i步可行的不同方式数目。

2.当前子问题vec[i]与前面子问题的关系：如果是用两步跳到当前（第i步），因为这两步已经确定，所以只有vec[i-2]种方法，即vec[i]=vec[i-2]；

如果使用一步跳到当前，因为这一步已经确定，所以只有vec[i-1]种方法，即vec[i]=vec[i-1]。

3.i==1或i==2时，vec[i]=i;i>2时，vec[i]=vec[i-1]+vec[i-2]。

4.时间复杂度：O(n)

空间复杂度：O(n)

class Solution {

public:

int climbStairs(int n) {

if(n == 1 || n == 2){

return n;

}else{

return climbStairs(n-1)+climbStairs(n-2);

}

}

};

方法二：用循环代替递归。递归需要多次调用原函数，但本题中只用到前两步的值，因此可以用变量记录，降低其空间复杂度为O(1)。 

 

class Solution {

public:

int climbStairs(int n) {

int result = 0;

int num1 = 0;

int num2 = 1;

for(int i=1;i<=n;++i){

result = num1+num2;

num1 = num2;

num2 = result;

}

return result;

}

};

                      

总结

以上是内存溢出为你收集整理的C++实现 LeetCode-70. Climbing Stairs全部内容，希望文章能够帮你解决C++实现 LeetCode-70. Climbing Stairs所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。