數樓梯(加強版)

題目背景:

  小明一天放學回家,看到從1樓到2樓共有n個台階,因為好奇,他想嘗試一下總共有幾種方案到二樓?他可以1步,2步,3步的跳,不能跳3步以上.

  他試了很多次都沒有解決這個問題,于是請求聰明的你幫忙解決這個問題.

題目描述:

1樓到2樓樓梯有n級台階。小明每次可以爬一格、走兩格或者跨三格。問最終有幾種方案到二樓？答案對998244353取模。

輸入格式:

一行一個數n。

輸出格式:

一行一個數，表示方案數。

輸入輸出樣例

輸入 #1:

3      

輸出 #1:

4      

輸入 #2:

5      

輸出 #2:

13      

提示說明:

 n≤1000  

 時間：1000ms   

 空間：256M  

 (上樓梯時不能往回走)

 如果覺得這道題太難可以前往P1255先做數樓梯簡單版：

 https://www.luogu.com.cn/problem/P1255

思路:

  1.暴力法

  很容易看出來，這是一道遞歸題，我們可以用暴力遞歸來解決。

#include<iostream> 
using namespace std; 
static const int mod=998244353;
long long sum=0;
int n;
long long fun(int x){
	if(x==n)
	  return 1;
	if(x>n)
	  return 0;
	long long s1=0,s2=0,s3=0;
	s1+=fun(x+1)%mod;
	s2+=fun(x+2)%mod;
	s3+=fun(x+3)%mod;
	return (s1+s2+s3)%mod;
}
int main(){
	cin>>n;
	cout<<fun(0)<<endl;		
    return 0;
}
           

但是這個份代碼會逾時，非常慢，是以要進行優化！

2.遞推法

我們用 f(x) 表示爬到第 x 級台階的方案數，考慮最後一步可能跨了一級台階，也可能跨了兩級台階，是以我們可以列出如下式子：

f(x)=f(x−1)+f(x−2)

它意味着爬到第 x 級台階的方案數是爬到第 x−1 級台階的方案數和爬到第 x−2 級台階的方案數的和。很好了解，因為每次隻能爬 1 級或 2 級，是以 f(x) 隻能從 f(x−1)和 f(x−2) 轉移過來，而這裡要統計方案總數，我們就需要對這兩項的貢獻求和。

  以上是動态規劃的轉移方程，下面我們來讨論邊界條件。我們是從第 0 級開始爬的，是以從第 0 級爬到第 0 級我們可以看作隻有一種方案，即 f(0)=1；從第 0 級到第 1 級也隻有一種方案，即爬一級，f(1)=1。這兩個作為邊界條件就可以繼續向後推導出第 n 級的正确結果。我們不妨寫幾項來驗證一下，根據轉移方程得到 f(2)=2，f(3)=3，f(4)=5，……，我們把這些情況都枚舉出來，發現計算的結果是正确的。

  我們不難通過轉移方程和邊界條件給出一個時間複雜度和空間複雜度都是 O(n)的實作，但是由于這裡的 f(x) 隻和 f(x−1)) 與 f(x−2)有關，是以我們可以用「滾動數組思想」把空間複雜度優化成 O(1)。下面的代碼中給出的就是這種實作。

#include<iostream> 
using namespace std; 
static const int mod=998244353;
void fun(int n){
	long long max[1001];
	int i=0;
	max[0]=1;
	max[1]=2;
	max[2]=4;
	for(int j=3;j<n;j++)
	  max[j]=(max[j-1]+max[j-2]+max[j-3])%mod;
	cout<<max[n-1]<<endl;
}
int main(){
	int n;
	cin>>n;
	fun(n);		
    return 0;
}
           

總結：

  對于這道題，有些像斐波那契數列，需要将遞歸進行優化才可以解決。

題目連結：

數樓梯(加強版) - 洛谷

https://www.luogu.com.cn/problem/U267577