백준 1520 - 내리막 길 (파이썬)

Answer

import sys
input = sys.stdin.readline
m, n = map(int, input().split())

a = [list(map(int, input().split())) for _ in range(m)]
dp = [[-1] * n for _ in range(m)]

def dfs(y, x):
    if x == n - 1 and y == m - 1:
        return 1
    if dp[y][x] != -1:
        return dp[y][x]

    dp[y][x] = 0

    for dx, dy in (1, 0), (0, 1), (-1, 0), (0, -1):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < n and 0 <= ny < m:
            if a[ny][nx] < a[y][x]:
                dp[y][x] += dfs(ny, nx)

    return dp[y][x]

print(dfs(0, 0))