[백준] 1520 내리막길

---

지도의 (0, 0) 지점에서 (M-1, N-1)까지 내리막길로 이동할 수 있는 경로의 수를 구하는 문제이다. 다이내믹 프로그래밍을 사용하여 해결 할 수 있다.

 

다이내믹 프로그래밍에는 Bottom-up 방식인 Tabulation 기법과 Top-down 방식인 Memoization 기법이 존재한다. Tabulation 기법은 보통 반복문으로 구현하며, Memoization은 보통 재귀 함수로 구현한다.

 

메모리나 시간 복잡도를 고려하였을 때 Memoization에 비해 Tabulation이 더  효율적이지만 상황에 따라 다르게 적용될 수 있으므로 두 가지 방법 모두 알고있어야 한다.

 

Tabulation 예제

// Tabulated version to find factorial x.
int dp[MAXN];

// base case
int dp[0] = 1;
for (int i = 1; i< =n; i++)
{
    dp[i] = dp[i-1] * i;
}

Memoization 예제

// Memoized version to find factorial x.
// To speed up we store the values
// of calculated states

// initialized to -1
int dp[MAXN]

// return fact x!
int solve(int x)
{
    if (x==0)
        return 1;
    if (dp[x]!=-1)
        return dp[x];
    return (dp[x] = x * solve(x-1));
}

 

내리막길 문제는 Memoization으로 해결할 수 있다.