problem-1520

과정
*처음에 dfs로만 풀었는데, 이럴 경우 시간 초과가 발생 -> dp를 이용해야한다.
1.dfs(x,y)를 통해 낮은 곳으로만 이동 -> visited함수는 필요없음 why? 작은 곳으로만 이동하기 때문에 그 전 노드로는 가지 않게 됨
2. 2차원 dp설정 -> dp[x][y] = x,y에서부터 target까지의 경로 수
3. dfs에서 target에 도착하면 return 1
4. dp[x][y]!=-1이면 기존에 저장해둔 값을 리턴

import sys
input=sys.stdin.readline

n,m = map(int,input().split())
board=[]
for i in range(n):
    board.append(list(map(int,input().split())))

dx=[1,0,-1,0]
dy=[0,1,0,-1]

answer=0

dp = [[-1 for i in range(m)] for j in range(n)]
def dfs(x,y):
    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 and ny>=0 and nx<n and ny<m:
            if board[nx][ny]<board[x][y]:
                dp[x][y]+=dfs(nx,ny)
    return dp[x][y]

if board[0][0]>board[n-1][m-1]:
    answer = dfs(0,0)
print(answer)

time:30분
resolve:O 다시풀장 dp사용법을 참고해버림