[プログラマー/Python]ダイナミックプログラミング通学路

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

アルゴリズム分類

動的プログラミング

問題を解く

시간초과코드
def solution(m, n, puddles):
from collections import deque
dx=[1,0]
dy=[0,1]

kx=[-1,0]
ky=[0,-1]
graph=[[0]*m for i in range(n)]

for i in puddles:
    x,y=i
    graph[y-1][x-1]=-1
graph[0][0]=1

queue=deque()
queue.append((0,0))
while queue:
    x,y=queue.popleft()
    if x==n-1 and y==m-1:
        break
    for i in range(2):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx>=n or ny>=m:
            continue
        elif graph[nx][ny]==0:
            cnt=0
            for j in range(2):
                xx=nx+kx[j]
                yy=ny+ky[j]
                if xx<0 or yy<0:
                    continue 
                elif graph[xx][yy]!=-1:
                    cnt+=graph[xx][yy]
            graph[nx][ny]=cnt
        queue.append((nx,ny))

return (graph[n-1][m-1]%1000000007)

bfsはタイムアウトに失敗したので2回回転した.
0に初期化された横、縦に1行ずつ加え、出発点となる家屋の位置の値は1とする.
各座標に左上の値を加えればいいです.
graph=[[0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 1, 0, 1, 2], [0, 1, 1, 2, 4]]

ソースコード

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

    for i in range(1,n+1):
        for j in range(1,m+1):
            if [j,i] in puddles:
                continue
            if i==1 and j==1:
                continue
            graph[i][j]=graph[i-1][j]+graph[i][j-1]
    return (graph[n][m]%1000000007)