baekjun 1520. 내리막 길

 내리막길이므로 오는 방향의 캐싱을 고려할 필요가 없다.(어느 방향에서 오든 갈 수 있는 길은 왔던 길의 영향을 받지 않기때문)

#include <iostream>
#include <cstring>
 
using namespace std;
 
int M, N;
int map[500][500];
int cache[501][501];
 
int getDownhillPath(int y, int x) {
    if (y == M - 1 && x == N - 1) {
        return 1;
    }
    if (y < 0 || x <0 || y > M || x > N)
        return 0;
    int & ret = cache[y][x];
    if (ret != -1)
        return ret;
    ret = 0;
    if(map[y - 1][x] < map[y][x])
        ret += getDownhillPath(y - 1, x);
    if(map[y][x - 1] < map[y][x])
        ret += getDownhillPath(y, x - 1);
    if(map[y + 1][x] < map[y][x])
        ret += getDownhillPath(y + 1, x);
    if(map[y][x + 1] < map[y][x])
        ret += getDownhillPath(y, x + 1);
    return ret;
}
 
int main() {
    cin >> M >> N;
    memset(cache, -1, sizeof(cache));
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            cin >> map[i][j];
    cout << getDownhillPath(0, 0) << endl;
    //system("pause");
    return 0;
}

#include <iostream>
#include <cstring>
 
using namespace std;
int N, M;
int paths[501][501];
int cache[501][501];
int tbrl[4][2] = {{1,0}, {0, 1}, {-1, 0}, {0, -1}};
 
int isInPath(int y, int x){
    return (y > 0) && (x > 0) && (y <= N) && (x <= M);
}
 
int findPath(int y, int x){ // start 1, 1
    if(y == N && x == M)
        return 1;
    if(cache[y][x] != -1)
        return cache[y][x];
    int &ret = cache[y][x];
    ret = 0;
    for(int i = 0; i < 4; i++){
        int yi = y + tbrl[i][0];
        int xi = x + tbrl[i][1];
        if(isInPath(yi, xi) && paths[y][x] > paths[yi][xi]){
            ret += findPath(yi, xi);
        }
    }
    return ret;
}
 
int main(){
    cin >> N >> M;
    memset(cache, -1, sizeof(cache));
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> paths[i][j];
        }
    }
    cout << findPath(1, 1);
    return 0;
}