2022.12.30 PM 10:00 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=d212 出題者 : s0928571036 標籤 : DP(動態規劃) 難易度 : 3
解題想法 : 首先可以先思考,假如我們現在位在第k層階梯,那我們是從哪一階來的? 根據題意,應該可以很清楚的知道,不是從前面一階的地方來的,就是從前面兩階的地方來的(因為只會有走一步or走兩步的可能)。 回歸問題,我們要如何知道當走到第n層階梯時有多少方法? 首先走到n的方法有兩種 : 從n-1來或從n-2來,因此走到n的方法數 = 走到n-1的方法數 + 走到n-2的方法數,到這裡就會很清楚地得知,我們要如何DP了。 首先定義dp[i]為在第i階時所需要的方法數,由於走一階的方法只有一種,因此dp[1] = 1,而走兩階的方法則有兩種(走兩次一步 or 走一次兩步),故dp[2] = 2,再來就可以根據剛才的分析得出轉移式 dp[i] = dp[i-1] + dp[i-2],很驚訝的會發現,這不就是費氏數列嗎? 事實上,就是費氏數列沒錯。 (如果不知道費氏數列是什麼,可以參考此文 : https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0) ※注意題目為多筆測資,因此要讀到沒有資料為止。 ※本題C採用Bottom-up實作,C++採用Top-down,Python則兩者皆有。 ※Top-down v.s Bottom-up : https://yuihuang.com/dp-top-down-vs-bottom-up/ ※若使用C/C++解題,dp[]需要使用long long,因為當n為100時,數量級是很驚人的。
//C language
#include<stdio.h>
typedef long long LL;
int main(){
int N;
LL dp[105];
dp[1]=1; dp[2]=2;
for(int i=3;i<105;i++){
dp[i]=dp[i-1]+dp[i-2];
}
while(scanf("%d",&N)!=EOF){
printf("%lld\n",dp[N]);
}
return 0;
}

//C++ language
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
vector<LL>dp(105,-1);
LL DP(int N){
if(dp[N]!=-1) return dp[N];
dp[N]=DP(N-1)+DP(N-2);
return dp[N];
}
int main(){
int N;
dp[1]=1; dp[2]=2;
while(cin>>N){
cout<<DP(N)<<"\n";
}
return 0;
}

## Python language
#Top-down
from sys import stdin
dp=[0,1,2]+[-1]*105
def DP(n):
if dp[n]!=-1: return dp[n]
dp[n]=DP(n-1)+DP(n-2)
return dp[n]
for read in stdin:
n=int(read)
print(DP(n))
#Bottom-up
from sys import stdin
dp=[0,1,2]+[-1]*105
for i in range(3,105): dp[i]=dp[i-1]+dp[i-2]
for read in stdin:
n=int(read)
print(dp[n])
