[dps, dp] 백준 1520 내리막 길

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

처음에 bfs로 풀었다가 메모리초과가 떴었습니다.

이번 문제는 다른 사람들의 소스를 참고하면서 짰습니다...

#include <iostream>
#include <queue>
using namespace std;
 
int map[501][501] = {0};
int mem[501][501] = {0};
int dy[4] = {1,-1,0,0};
int dx[4] = {0,0,1,-1};
 
 
int M, N; //세로, 가로
 
 
int dfs(int x, int y);
 
int main(){
    ios_base::sync_with_stdio(false);
    mem[1][1] = 1;
    cin >> M >> N;
    
    for(int i = 1; i <= M; i++){
        for(int j = 1; j <= N; j++){
            cin >> map[i][j];
            mem[i][j] = -1;
        }
    }
    
    cout << dfs(1,1);
    
}
 
int dfs(int x, int y){
    
    if(mem[y][x] != -1) return mem[y][x];
    if(x==N && y == M) return 1;
    
    mem[y][x] = 0;
    for(int i = 0; i < 4; i++){
        int nextx = x + dx[i];int nexty = y + dy[i];
        if(nextx>0 && nextx <= N && nexty > 0 && nexty <= M && map[nexty][nextx] <map[y][x])
            mem[y][x] += dfs(nextx,nexty);
    }
    
    return mem[y][x];
}

1520