洛谷【C++編程基礎(chǔ)】遞歸函數(shù)初步專題解題報(bào)告-創(chuàng)新互聯(lián)

題目描述
樓梯有n階臺(tái)階,上樓可以一步上一階,也可以一步上二階。用遞歸的方法編一程序計(jì)算共有多少種不同的走法。（試用遞歸完成，會(huì)出現(xiàn)什么問題，如何解決）
輸入格式
一個(gè)正整數(shù)n（n不超過90）
輸出格式
一個(gè)整數(shù)，表示走法方案數(shù)。
輸入輸出樣例
輸入
4
輸出
5

題目出處
我第一秒想到的是暴力……（造化低了）33分

#includeusing namespace std;

int n,cnt;

void f(int s){if(s==n){++cnt;
		return;
	}
	if(s>n)return;
	for(int i=1;i<=2;++i)
		f(s+i);
	return;
}

int main(){cin>>n;
	f(0);
	cout<

仔細(xì)對(duì)比數(shù)據(jù)，竟發(fā)現(xiàn)答案是斐波那契數(shù)列！??！
自制奇葩遞歸

#includeusing namespace std;

long long n,ans,vh[100];

void f(int s){if(s<3){if(s==2)cout<<3<cout<vh[0]=1;//這一行加上只是為了對(duì)比發(fā)現(xiàn)斐波那契，可刪除
	vh[1]=1;
	vh[2]=2;
	cin>>n;
	f(3);
	return 0;
}

標(biāo)程：

#includeusing namespace std; 

long long dp[110];//記憶化
long long f(long long n){if(dp[n])return dp[n];
	if(n<=2)return n;//注意這個(gè)地方與標(biāo)準(zhǔn)斐波那契不同（因?yàn)檫@一題第n個(gè)答案是第(n+1)個(gè)斐波那契數(shù)，忘記的同學(xué)可以向上翻翻T7，這里原是return 1）
	else dp[n]=f(n-1)+f(n-2);
	return dp[n];
}

int main(){int n;
	cin>>n;
	cout<

刨根問底的同學(xué)可以繼續(xù)看：
QUESTION:為什么答案是斐波那契數(shù)列？
ANSWER:上面我們用的是歸納的方法。下面主要介紹原因：
第1,2個(gè)臺(tái)階分別有1,2種走法（1）（1+1或2）
而從第3個(gè)開始，每一個(gè)數(shù)目（假設(shè)是第n個(gè)（n>2））都可以理解為第(n-1)的走法再走1級(jí)臺(tái)階或第(n-2)的走法再走2級(jí)臺(tái)階，自然就有第(n-1)，第(n-2)的走法總數(shù)和數(shù)量的方法。