d212. 東東爬階梯

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])

相關文章