d810 - 大朋友下樓梯

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在不同難度下，從 0 樓走到地下 k 樓的方法數。難度決定了每次可以下降的樓梯數：簡單 (1 格)、中等 (1 或 2 格)、困難 (1 或 2 或 3 格)。 k 是一個負數，表示地下樓層。

解題思路

題目可以轉換為計算到達每個樓層的方法數。對於簡單難度，到達第 i 樓的方法數等於到達第 i-1 樓的方法數。對於中等難度，到達第 i 樓的方法數等於到達第 i-1 樓和第 i-2 樓的方法數之和。對於困難難度，到達第 i 樓的方法數等於到達第 i-1 樓、第 i-2 樓和第 i-3 樓的方法數之和。

程式碼預先計算了從 0 到 -20 樓的每種難度的到達方法數，並儲存在 b (中等難度) 和 c (困難難度) 陣列中。然後，對於每個測試案例，根據輸入的難度 a 和地下樓層 n，從預先計算的陣列中獲取結果並輸出。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <stdio.h>
int b[21]={1},c[21]={1};
int main(){
	int a,n;
	for(int i=0;i<=20;i++){
		b[i+1]+=b[i];
		b[i+2]+=b[i];
		c[i+1]+=c[i];
		c[i+2]+=c[i];
		c[i+3]+=c[i];
	}
	while(scanf("%d %d",&a,&n)>0){
		if(a==1)
			printf("1\n");
		else if(a==2){
			n*=-1;
			printf("%d\n",b[n]);
		}
		else{
			n*=-1;
			printf("%d\n",c[n]);
		}
	}
}