力扣70. 爬楼梯（递归、动态规划、斐波那契数列）_递归爬楼梯复杂度

力扣70. 爬楼梯

https://leetcode-cn.com/problems/climbing-stairs/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

 

方法：递归、动态规划、斐波那契数列

#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;
class Solution 
{
public:
	//递归，超时
	int climbStairsrecursive(int n)
	{
		int k = 0;
		//递归
		recursive(n,k);
		return k;
	}
	void recursive(int x, int &k)
	{
		//递归终止
		if (x == 0)
		{
			k++;
			return;
		}
		//跳1级
		if (x - 1 >= 0)recursive(x - 1,k);
		//跳2级
		if (x - 2 >= 0)recursive(x - 2,k);
	}
	//动态规划
	int climbStairsdynamic(int n)
	{
		vector<int>result;
		result.push_back(1); result.push_back(1);
		int i = 2;
		while (n >= i)
		{
			//到达第 i 阶的方法总数就是到第 (i-1) 阶和第 (i-2) 阶的方法数之和
			int temp = result[i - 1] + result[i - 2];
			result.push_back(temp);
			i++;
		}
		return result[n];
	}
	//斐波那契数Fibonacci sequence
    //思路和动态规划一样，只不过空间复杂度：O(1)使用常量级空间
	int climbStairsfib(int n)
	{
		int f = 0;
		int g = 1;
		int i = 1;
		while (n >= i)
		{
			//到达第 i 阶的方法总数就是到第 (i-1) 阶和第 (i-2) 阶的方法数之和
			g = f + g;
			f = g - f;
			i++;
		}
		return g;
	}
};
 
 
int main()
{
	Solution s;
	for (int i=0;i<=30;i++)
	{
		auto resultrecursive = s.climbStairsrecursive(i);
		auto resultdynamic = s.climbStairsdynamic(i);
		auto resultfib = s.climbStairsfib(i);
		cout << i << "递归：" << resultrecursive << '\t' << "动态规划：" << resultdynamic << '\t' << "斐波那契数：" << resultfib<<'\n';
		if ((resultrecursive != resultdynamic) || (resultrecursive != resultfib))
		{
			cout << '\n' << '\n' << "error" << '\n' << '\n';
			break;
		}
	}
    return 0;
}

一、递归

复杂度分析

• 时间复杂度：O(2^n)，树形递归的大小为 2^n    所以会超时

• 空间复杂度：O(n)，递归树的深度可以达到 n

• 在 n = 5 时的递归树将是这样的：

上图来源力扣官方解析：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode/

//递归，超时
	int climbStairsrecursive(int n)
	{
		int k = 0;
		//递归
		recursive(n,k);
		return k;
	}
	void recursive(int x, int &k)
	{
		//递归终止
		if (x == 0)
		{
			k++;
			return;
		}
		//跳1级
		if (x - 1 >= 0)recursive(x - 1,k);
		//跳2级
		if (x - 2 >= 0)recursive(x - 2,k);
	}

二、动态规划

复杂度分析

• 时间复杂度：O(n)，单循环到 n 。

• 空间复杂度：O(n)，dp 数组用了 n 的空间。

思路：

第 i 阶可以由以下两种方法得到：

在第 (i-1)阶后向上爬1阶。

在第 (i-2)阶后向上爬 2 阶。

所以到达第 i 阶的方法总数就是到第 (i-1)阶和第 (i-2)阶的方法数之和。

	//动态规划
	int climbStairsdynamic(int n)
	{
		vector<int>result;
		result.push_back(1); result.push_back(1);
		int i = 2;
		while (n >= i)
		{
			//到达第 i 阶的方法总数就是到第 (i-1) 阶和第 (i-2) 阶的方法数之和
			int temp = result[i - 1] + result[i - 2];
			result.push_back(temp);
			i++;
		}
		return result[n];
	}

三、斐波那契数列

Fib(n)=Fib(n−1)+Fib(n−2)

 

Fib(0)=1，Fib(1)=1，Fib(2)=2,

复杂度分析

• 时间复杂度：O(n)，单循环到 n，需要计算第 n 个斐波那契数。

• 空间复杂度：O(1)，使用常量级空间。

//斐波那契数Fibonacci sequence
	//思路和动态规划一样，只不过空间复杂度：O(1)使用常量级空间
	int climbStairsfib(int n)
	{
		int f = 0;
		int g = 1;
		int i = 1;
		while (n >= i)
		{
			//到达第 i 阶的方法总数就是到第 (i-1) 阶和第 (i-2) 阶的方法数之和
			g = f + g;
			f = g - f;
			i++;
		}
		return g;
	}