走楼梯问题 题解

走楼梯问题
题目：
有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
比如，每次走1级台阶，一共走10步，这是其中一种走法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。
再比如，每次走2级台阶，一共走5步，这是另一种走法。我们可以简写成 2,2,2,2,2。
当然，除此之外，还有很多很多种走法。
如何求解这个问题？
排列组合思想写多层的嵌套循环遍历所有可能的解。每遍历一次，计数器加一。
时间复杂度是指数级。

long long ans=0;
void dfs(int n)
{
	if (n==0) ans++;
	else
	{
		if (n-1>=0)dfs(n-1);
		if (n-2>=0)dfs(n-2);
	}
}

递归调用图示

如何求解这个问题？

动态规划思想(大事化小，小事化了)
试想一下假设你只差最后一步走到第10个台阶，这种会有几种情况？
两种。
一种是从第9阶一步走一级台阶上来。
另一种是从第8阶一步走两级台阶上来。
现在假设从第0阶走到第9阶有x种走法，从第0阶走到第8阶有y种走法，问：从第0阶走到第10阶有几种走法？
x+y
为表达方便设f(m)表示从第0阶到第m阶的走法，那么f(10)=f(9)+f(8)。如果计算f(9)和f(8)。
只有1个台阶或2个台阶有多少种走法？
f(1)=1
f(2)=2;
f(n)=f(n-1)+f(n-2) (n>=3)
动态规划三个基本概念
最优子结构
边界
状态转移公式
f(9)，f(8)就是f(10)的最优子结构。
f(1)，f(2)就是边界。
f(n)=f(n-1)+f(n-2) 就是状态转移方程。
如何写代码?
方法一：递归求解O(2ⁿ)

long long fib(int n)
{
	if (n<=2) return n;
	else return fib(n-1)+fib(n-2);	
} 

从下图中发现递归求解过程中存在大量重复计算。

如何避免大量的重复计算？我们可以开一个数组来保存计算的结果，下次进行计算前先看一个这个过程是否已经计算过，计算过，直接从数组中取出来。

方法二：记忆化O(n)

memset(F,-1,sizeof(F));
long long fib(int n)
{
	if (F[n]!=-1) return F[n];
	if (n<=2) return F[n]=n;
	else return F[n]=fib(n-1)+fib(n-2);	  
}

这是动态规划的方法。
刚才我们是从所有求的结果向已知的方向递归求解，现在可以从开始向结果递推求解。

方法三：递推求解O(n)

long long fib(int n)
{
	F[1]=1;
	F[2]=2;
	for (int i=3;i<=n;i++)
	{
		F[n]=F[n-1]+F[n-2]	
	}
	return F[n];	  
}