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

相關文章

分享此文：