LeetCode 70. 爬楼梯 C/C++/Python-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 70. 爬楼梯 C/C++/Python。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

边走边c上楼梯,算法题LeetCode【C/C++/Python题解】,leetcode,c语言,c++,Python,算法

欢迎关注博主 Mindtechnist 或加入【Linux C/C++/Python社区】一起探讨和分享Linux C/C++/Python/Shell编程、机器人技术、机器学习、机器视觉、嵌入式AI相关领域的知识和技术。

专栏：LeetCode刷题

题目描述

假设你正在爬楼梯。需要 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

C语言版

/*70_爬楼梯*/

/*动态规划  f(n)=f(n-1)+f(n-2)*/
int climbStairs(int n) {
	int i = 0;
	int ret[46];
	ret[0] = 1;
	ret[1] = 1;
	if (n > 1)
	{
		for (i = 2; i <= n; i++)
		{
			ret[i] = ret[i - 1] + ret[i - 2];
		}
	}
	return ret[n];
}

/*优化
因为在递推公式中，我们只需要f(n-1),f(n-2)来退出n对应的总类，n-2之前的数据无需保留
所以只用三个数来记录状态即可(滚动)，不需用数组来记录所有值
*/
int climbStairs(int n) {
	int i = 0;
	int num1 = 0, num2 = 0, num3 = 1;
	for (i = 0; i < n; i++)
	{
		num1 = num2;
		num2 = num3;
		num3 = num1 + num2;
	}
	return num3;
}

C++版

//70_爬楼梯

class Solution {
public:
	int climbStairs(int n) {
		vector<int> ret;
		ret.push_back(1);
		ret.push_back(1);
		if (n > 1)
		{
			for (int i = 2; i <= n; i++)
			{
				ret.push_back(ret[i - 1] + ret[i - 2]);
			}
		}
		return ret[n];
	}
};

//优化
class Solution {
public:
	int climbStairs(int n) {
		int num1 = 0, num2 = 0, num3 = 1;
		for (int i = 0; i < n; i++)
		{
			num1 = num2;
			num2 = num3;
			num3 = num1 + num2;
		}
		return num3;
	}
};

Python版

class Solution:
    def climbStairs(self, n: int) -> int:
        f = list()
        f.append(1)
        f.append(1)
        if n < 2:
            return f[n]
        for i in range(2, n + 1):
            f.append(f[i - 1] + f[i - 2])
        return f[n]
		
#优化空间复杂度
class Solution:
    def climbStairs(self, n: int) -> int:
        num1, num2, num3 = 0, 0, 1
        for i in range(n):
            num1 = num2
            num2 = num3
            num3 = num1 + num2
        return num3