首页 > 代码库 > [LeetCode系列]爬梯问题的递归解法转换为迭代解法
[LeetCode系列]爬梯问题的递归解法转换为迭代解法
有一个n阶的梯子, 你每次只能爬1阶或2阶, 请问共有多少种登顶的爬法?(正好爬完n阶, 不能多也不能少)
本题最优解是直接套用菲波那切数列即可(因为菲波那切数列的第n个元素正好等于第n-1个元素和第n-2个元素的和, 与本题的要求完全相同).
递归解法:
1 int climbStairs(int n) {2 if (n < 3) return n;3 return climbStairs(n-1) + climbStairs(n-2);4 }思路很清晰, 递归到当前阶数小于3阶时返回种类(因为比较容易计算, 并非一定是3阶), 这也是求解菲波那切数列的递归解法.
然而实际中这种解法对栈要求过大, 非常容易溢出. 因此有必要转化为迭代算法:
1 int climbStairs(int n) {2 vector<int> count(n+1);3 count[0] = 0;4 count[1] = 1;5 count[2] = 2;6 for (int i = 3; i <= n; i++)7 count[i] = count[i-1] + count[i-2];8 return count[n];9 }简单总结一下: 从递归->迭代时, 只需要把思考过程转换为这种数列求解的思路, 从前几个元素开始向后推导即可, 推导的关系则与递归的返回表达式非常相似.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。