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;

}

};

? ? ? ? ? ? ? ? ? ? ??

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!