[백준] 1520번 내리막길

문제 링크: https://www.acmicpc.net/problem/1520

문제

입출력

문제 접근

dp문제이다.
단순한 문제이다. dfs와 dp랑 섞여있는 문제이다. edge는 현재 자신의 높이 보다 작은 node들로만 연결되어 있고, 단방향 graph이다.
현재 위치에서 목적지에 도착할 수 있는 경로가 몇가지인지 계산하고 그것들을 전에 node에 전해줘서 전에 node는 자기와 연결되어 있는 모든 node에서 목적지로 갈수 있는 경우의 수를 구하면 된다.

코드 구현(c++)

#include <iostream>
#include <cstring>

using namespace std;

int map[501][501];
int cache[501][501];
int M, N;
int xMove[4] = {0,0,1,-1};
int yMove[4] = {-1,1,0,0};
int dp(int i, int j){
    if(i == M - 1 && j == N - 1) return 1;
    int& res = cache[i][j];
    if(res != -1) return res;
    res = 0;
    for(int k = 0 ; k < 4 ; k++){
        int nextI = i + yMove[k]; int nextJ = j + xMove[k];
        if(nextI < 0 || nextJ < 0 || nextI >= M || nextJ >= N ) continue;
        if(map[i][j] <= map[nextI][nextJ]) continue;
        res += dp(nextI, nextJ);
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> M >> N;
    for(int i = 0 ; i < M ; i++){
        for(int j = 0 ; j < N ; j++){
            cin >> map[i][j];
        }
    }
    memset(cache, -1, sizeof(cache));
    cout << dp(0,0) << "\n";
}