문제

https://school.programmers.co.kr/learn/courses/30/lessons/42898

풀이

문제를 보고 바로 동적계획법을 떠올렸다. 요즘 top-down으로 dp를 해결하는 것을 연습하고 있어서 top-down으로 풀어봤다.
예제가 제대로 나오고 생각한대로 dp 배열이 채워졌는데 계속 틀려서 의문이였는데 좌표가 (m, n) 이였다;;

문제를 제대로 읽고 풀자!!

CODE

def solution(m, n, puddles):
    mod = 1000000007
    
    dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]
    
    def get_dp(r, c):
        if r == 1 and c == 1:
            return 1
        
        if r < 1 or c < 1 or [c, r] in puddles:
            return 0
        
        if dp[r][c] != -1:
            return dp[r][c]
        
        dp[r][c] = (get_dp(r-1, c) + get_dp(r, c-1))
        
        return dp[r][c] % mod
    
    answer = get_dp(n, m)
    
    return answer