网站及备案,后台网站模板 html,wordpress模板 多梦,消耗品分类【LetMeFly】70.爬楼梯#xff1a;动态规划#xff08;递推#xff09;
力扣题目链接#xff1a;https://leetcode.cn/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#x…【LetMeFly】70.爬楼梯动态规划递推
力扣题目链接https://leetcode.cn/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 示例 1
输入n 2
输出2
解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶
示例 2
输入n 3
输出3
解释有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶提示
1 n 45
方法一动态规划递推
第 i i i阶楼梯可以由第 i − 1 i-1 i−1阶或 i − 2 i-2 i−2阶楼梯而来因此只需要将相邻两阶的方案数加起来就能得到下一阶的方案数。
初始值 0 0 0阶楼梯的方案数为 1 1 1 1 1 1阶楼梯的方案数为 1 1 1。
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
class Solution {
public:int climbStairs(int n) {int _0 1, _1 1;for (int i 2; i n; i) {int _2 _0 _1;_0 _1, _1 _2;}return _1;}
};Python
class Solution:def climbStairs(self, n: int) - int:_0, _1 1, 1for i in range(n - 1):_0, _1 _1, _0 _1return _1同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/134913892
