[BOJ/백준] 1520 내리막길

def dfs(x,y):
    global N,M
    if x == N-1 and y == M-1:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    else:
        dp[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if arr[nx][ny] < arr[x][y]:
                    dp[x][y] += dfs(nx,ny)
        return dp[x][y]
 
 
 
import sys
 
input = sys.stdin.readline
 
N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*M for _ in range(N)]
print(dfs(0,0))

DP 와 DFS가 결합된 문제였다. 최소로 도달한거리를 DP에 저장해서 얻는것이었다. 마지막 우리가 도달해야하는 위치만 초기값을 1로 주고, 나머지는 전부 0으로 초기화한뒤 역으로 계싼해서 오는것이다.