stage t=i+j, t=0..m+n

state (i, j): 정점, i=0..n, j=0..m (i=n or j=m are dummies)

ret func f(i, j): (i, j)에서 (n-1, m-1)까지 직각 거리

BE: f(i, j) = 1 + min{f(i+1, j), f(i, j+1)}

BC: f(n-1, m-1) = 0

f(n, j) = f(i, m) = puddle의 ret func 값 = INF

Obj: f(0, 0)

def solution(m, n, puddles):
    ret = {i:[0]*(m+1) for i in range(n+1)}
    ret[n-1][m-1] = 1

    puddles = {(y-1, x-1) for x, y in puddles}
    puddles.add((n-1, m-1))  # 도착지는 0 고정이므로 갱신 X

    for i in range(n-1, -1, -1):
        for j in range(m-1, -1, -1):
            if (i, j) not in puddles:
                ret[i][j] = ret[i+1][j] + ret[i][j+1]

    return ret[0][0] % 1000000007

for t in range(n+m-2, -1, -1):
        for i in range(t-n, n):  # todo

위처럼 stage를 i+j로 하는 대신, 그냥 한 행 씩 우측부터 계산해도 오른쪽 아래 모두 합산 가능하다.

for i in range(n-1, -1, -1):
        for j in range(m-1, -1, -1):

다시 풀기

'''
state (x, y): 좌표
ret[x, y]: (x, y)에서 (m, n)까지 최단 경로 개수
BE: ret[x, y] = ret[x+1, y] + ret[x, y+1]
BC: ret[m, n] = 1, ret[m+1, y] = 0, ret[x, n+1] = 0, ret[puddle] = 0
Obj: ret[1, 1]
'''
from itertools import product

def solution(m, n, puddles):
    ret = {(x, y): 0 for x, y in puddles}
    ret.update({(m+1, y): 0 for y in range(1, n)})
    ret.update({(x, n+1): 0 for x in range(1, m)})
    ret[m, n] = 1
    
    for x, y in product(range(m, 0, -1), range(n, 0, -1)):
        if ret.get((x, y), None) is None:
            ret[x, y] = ret[x+1, y] + ret[x, y+1]
        
    return ret[1, 1] % (10**9 + 7)

def solution(m, n, puddles):
    ret = [[0]*(n+2) for _ in range(m+2)]
    ret[m][n] = 1
    puddles.append([m, n])
    
    for x, y in product(range(m, 0, -1), range(n, 0, -1)):
        if [x, y] not in puddles:
            ret[x][y] = ret[x+1][y] + ret[x][y+1]
        
    return ret[1][1] % (10**9 + 7)