백준 1520 내리막 길

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

문제 이해는 어렵지 않다.
dfs를 통해 시뮬레이션을 해보면서 경우의 수를 찾으면 된다.
근데 역시나 dfs만 쓰면 n과m이 500인 상황에서 시간초과가 날수밖에 없다.

이러한 상황에서 중복된 작업이 발생하는 지점은
어떤 지점을 방문 했을때 이미 그 자리에서 다른 상태에서 가지치기를 했었어서 가지수가 몇개인지 알 때이다.

그렇기 때문에 상태별 값을 저장해놓으면 좋겠다라고 생각했다.
(처음에 dp배열을 0으로 초기화해서 방문한 상태인지 값이 없는거지를 구분 안했었다... -1로 초기화를 하고 방문시 0으로 바꿔주는 센스가 있어야!)

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
n,m = map(int,input().split())
arr = []
for i in range(n):
    arr.append(list(map(int,input().split())))
dx = [-1,0,1,0]
dy = [0,1,0,-1]
dp = [[-1]*m for i in range(n)]
def dfs(x,y):
    global ans
    if x == n-1 and y == m-1:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    dp[x][y] = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if arr[x][y] > arr[nx][ny]:
            dp[x][y] += dfs(nx,ny)
    return dp[x][y]
dfs(0,0)
# for row in dp:
#     print(row)
print(dp[0][0])