原文: https://blog.csdn.net/rentiansky/article/details/60478228
问题描述:
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?
Note: Given n will be a positive integer.
关于这道题,想的方法是用斐波那契数列的方法去解。一开始用递归的方法,发现无法通过,查看原因是因为运行超时
class Solution {
public:
int climbStairs(int n) {
if (n<=2 && n>0)
return n;
return climbStairs(n-1)+ climbStairs(n-2);
}
};
显示结果:Time Limit Exceeded
后来修改代码,使用放弃递归使用数组来解,以减少时间复杂度,显示通过
class Solution {
public:
int climbStairs(int n) {
if (n<=2 && n>0)
return n;
int ways[n+1];
ways[1] = 1;
ways[2] = 2;
for (int i = 3;i<=n;i++)
ways[i] = ways[i-1] + ways[i-2];
return ways[n];
}
};
显示结果:Accepted
---------------------
作者:rentiansky
来源:CSDN
原文:https://blog.csdn.net/rentiansky/article/details/60478228
版权声明:本文为博主原创文章,转载请附上博文链接!
网友评论