洛谷P1255 数楼梯

题目描述

  楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。

  编一个程序，计算共有多少种不同的走法。

分析与代码

  走n阶楼梯，无论是走一次走1阶还是2阶，总得迈出一步，

  所以求n阶楼梯的走法数F(n)，可以看成是走F(n-1)和F(n-2)

  的和。

  而当楼梯只剩1阶时，就只有1种走法了；

       剩2阶时，可以选择1阶阶走，也可以直接走2阶，

       所以是2种走法；

  以此得出边界条件：n1 和 n2，可以很愉快的写出以下递归代码

#include<iostream>

using namespace std;

int F(int n){

	if(n==1)return 1;

	if(n==2)return 2;

	return F(n-1)+F(n-2);

}

int main(){

	int n;

	cin>>n;

	cout<<F(n)<<endl;

	return 0;

}

  很明显，简单递归会出现很多重复计算。

  如：F(n-2)会被F(n-1-1)计算一次，被F(n-2)计算一次。

  而回观上面我们写的函数返回表达式很容易让我们联想到

  斐波那契的递推式，由此可以得出DP的状态转移方程：

     F(1)=1 , F(2)=2 , F(n)=F(n-1)+F(n-2)

  其中n≥3。

#include<iostream>

using namespace std;

const int N=100010;

int F[N];

int main(){

	int n;

	cin>>n;

	F[1]=1;

	F[2]=2;

	for(int i=3;i<n;i++)F[i]=F[i-1]+F[i-2];

	return 0;

}

  到这里你以为完了吗？不！并没有！！！

  (如果你是有用Java和Python这种不太需要考虑数据范围的当我没说)

  本人亲测，int的话n到1500就炸了，long long到2000也不行...

  所以这题要AC还得用高精度！！！

(未完待续......)