백준: Gold4 - 1520, 1563

</br> 계속 계속
</br>

1520: 내리막 길

https://www.acmicpc.net/problem/1520

내리막길로만 이동할 때 길이 총 몇 가지가 있을까

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void func(int x, int y){
    int cnt = 0;
    if( dp[x][y] == -1 ) dp[x][y] = 0;
    if( x == n-1 && y == m-1 ){
        dp[x][y]++;
        return;
    }
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if( nx < 0 || n <= nx || ny < 0 || m <= ny ) continue;
        if( mmap[nx][ny] < mmap[x][y] ){
            if( dp[nx][ny] == -1 ){
                func(nx, ny);
            }
            dp[x][y] += dp[nx][ny];
        }
    }
}

dfs와 dp의 합작이다
내리막으로만 가기 때문에, 사이클이 있을 수 없어서 visited같은 배열은 딱히 필요 없다. dp가 체크해주기도 하고
그냥 dfs면 시간 초과가 난다. 예를 들어 백준에서 예제의 경우

ex)
4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

(1, 3)에 위치한 20은 (1,4)의 25와, (0, 3)의 32에서 갈 수도 있기 때문에 두 번 계산할 필요 없기 때문이다. 만약 4방향을 무조건 다 계산한다면 n과 m이 최대 500이므로 4^(500*500)이 될 거다.
따라서 최대한 줄여야 한다. 그런데, 탐색 후에도 dp가 0일 경우가 있으므로 dp를 -1로 초기화해야 한다.

ex)
4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

탐색 방향:
  4
2 O 1
  3

 0  0  0  0  0
-1 -1 -1  0  0
-1 -1 -1  0 -1
-1 -1 -1  1  1

...

 0  0  0  0  1
-1 -1 -1  1  1
-1 -1 -1  1 -1
-1 -1 -1  1  1

 0  0  0  2  1
-1 -1 -1  1  1
-1 -1 -1  1 -1
-1 -1 -1  1  1

...

 2  2  2  2  1
 0 -1 -1  1  1
 0 -1 -1  1 -1
 0  0  1  1  1

...

 2  2  2  2  1
 1 -1 -1  1  1
 1 -1 -1  1 -1
 1  1  1  1  1

 3  2  2  2  1
 1 -1 -1  1  1
 1 -1 -1  1 -1
 1  1  1  1  1

</br>

---

좋다
</br>