careercup-귀속과 동적 기획 9.1

9.1 어떤 아이가 계단을 오르고 있다. 계단은 n계단이 있고 아이는 한 번에 1계단, 2단계 또는 3계단을 올라갈 수 있다.아이가 계단을 오르는 방법이 얼마나 많은지 계산하는 방법을 실현한다.
해법:
우리는 위에서 아래로의 방식을 채택하여 이 문제를 해결할 수 있다.아이가 계단을 오르는 마지막 걸음, 즉 n 단계에 도착하는 걸음으로 1 단계, 2 단계 또는 3 단계를 걸을 수 있다.즉, 마지막 단계는 n-1 단계에서 1 단계, n-2 단계에서 2 단계로 올라가거나 n-3 단계에서 3 단계로 올라갈 수 있다.따라서 마지막 단계에 도달하는 주법은 사실 이 마지막 3단계에 도달하는 방식의 총체이다.
 
재귀적 접근 방식:

int countWaysD(int n)

{

    if(n<0)

        return 0;

    else if(n==0)

        return 1;

    else

    {

        return countWaysD(n-1)+countWaysD(n-2)+countWaysD(n-3);

    }

}

세 가지 임시 변수를 사용하는 방법:

int countWays(int n)

{

    if(n<0)

        return 0;

    if(n==0)

        return 1;

    int first=0,second=0,third=1;

    int i=1;

    int ret;

    while(i<=n)

    {

        ret=first+second+third;

        first=second;

        second=third;

        third=ret;

        i++;

    }

    return ret;

}

dp 방법을 사용하려면 앞에서 구한 값을 기록할 수 있는 그룹이 필요합니다.

int countWaysDP(int n,int dp[])

{

    if(n<0)

        return 0;

    if(n==0)

        return 1;

    if(dp[n]>0)

        return dp[n];

    else

        dp[n]=countWaysDP(n-1,dp)+countWaysDP(n-2,dp)+countWaysDP(n-3,dp);

    return dp[n];

}

C++ 구현 코드:

#include<iostream>

#include<cstring>

#include<climits>

using namespace std;



const int MAX=1000;



int countWaysD(int n)

{

    if(n<0)

        return 0;

    else if(n==0)

        return 1;

    else

    {

        return countWaysD(n-1)+countWaysD(n-2)+countWaysD(n-3);

    }

}

int countWays(int n)

{

    if(n<0)

        return 0;

    if(n==0)

        return 1;

    int first=0,second=0,third=1;

    int i=1;

    int ret;

    while(i<=n)

    {

        ret=first+second+third;

        first=second;

        second=third;

        third=ret;

        i++;

    }

    return ret;

}





int countWaysDP(int n,int dp[])

{

    if(n<0)

        return 0;

    if(n==0)

        return 1;

    if(dp[n]>0)

        return dp[n];

    else

        dp[n]=countWaysDP(n-1,dp)+countWaysDP(n-2,dp)+countWaysDP(n-3,dp);

    return dp[n];

}



int main()

{

    int dp[MAX]={0};

    for(int i=1; i<10; i++)

        cout<<countWays(i)<<endl;

}