Problem p02735 (python)

Fixed submission:
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
inf = 10 ** 9
dp = [[inf] * W for _ in range(H)]
dp[0][0] = 0 if s[0][0] == '.' else 1

for y in range(H):
    for x in range(W):
        if y < H - 1:
            dp[y + 1][x] = min(dp[y + 1][x], dp[y][x] +
                               (1 if s[y][x] == '.' and s[y + 1][x] == '#' else 0))
        if x < W - 1:
            dp[y][x + 1] = min(dp[y][x + 1], dp[y][x] +
                               (1 if s[y][x] == '.' and s[y][x + 1] == '#' else 0))

print(dp[-1][-1])

Buggy submission (verdict: Runtime Error):
def update(black):
    return '.' if black == '#' else '#'


def dp(i, j, w_end, h_end, black='#', memo={}):
    if (i, j, w_end, h_end, black) in memo:
        return memo[i, j, w_end, h_end, black]
    elif i < 0 or j < 0 or w_end >= W or h_end >= H:
        return float('inf')
    elif i == w_end and j == h_end:
        return 1 if grid[i][j] == black else 0
    elif grid[i][j] == black and grid[w_end][h_end] == black:
        not_flip = 1 + min(dp(i - 1, j, w_end, h_end, black, memo),
                           dp(i, j - 1, w_end, h_end, black, memo),
                           dp(i, j, w_end + 1, h_end, black, memo),
                           dp(i, j, w_end, h_end + 1, black, memo))
        new = update(black)
        flip = 1 + min(dp(i - 1, j, w_end + 1, h_end, new, memo),
                       dp(i - 1, j, w_end, h_end + 1, new, memo),
                       dp(i, j - 1, w_end + 1, h_end, new,  memo),
                       dp(i, j - 1, w_end, h_end + 1, new,  memo))
        res = min(not_flip, flip)
        memo[i, j, w_end, h_end, black] = res
        return res
    elif grid[i][j] == black:
        not_flip = 1 + min(dp(i - 1, j, w_end + 1, h_end, black, memo),
                           dp(i - 1, j, w_end, h_end + 1, black, memo),
                           dp(i, j - 1, w_end + 1, h_end, black, memo),
                           dp(i, j - 1, w_end, h_end + 1, black, memo))
        new = update(black)
        flip = 1 + min(dp(i - 1, j, w_end + 1, h_end + 1, new, memo),
                       dp(i, j - 1, w_end + 1, h_end + 1, new, memo))
        flip += min(dp(w_end + 1, h_end, w_end + 1, h_end, black, memo),
                    dp(w_end, h_end + 1, w_end, h_end + 1, black, memo))
        res = min(not_flip, flip)
        memo[i, j, w_end, h_end, black] = res
        return res
    elif grid[w_end][h_end] == black:
        not_flip = 1 + min(dp(i - 1, j, w_end + 1, h_end, black, memo),
                           dp(i - 1, j, w_end, h_end + 1, black, memo),
                           dp(i, j - 1, w_end + 1, h_end, black, memo),
                           dp(i, j - 1, w_end, h_end + 1, black, memo))
        new = update(black)
        flip = 1 + min(dp(i - 1, j - 1, w_end + 1, h_end, new, memo),
                       dp(i - 1, j - 1, w_end, h_end + 1, new, memo))
        flip += min(dp(i - 1, j, i - 1, j, black, memo),
                    dp(i, j - 1, i, j - 1, black, memo))
        res = min(not_flip, flip)
        memo[i, j, w_end, h_end, black] = res
        return res
    else:
        res = min(dp(i - 1, j, w_end + 1, h_end, black, memo),
                  dp(i - 1, j, w_end, h_end + 1, black, memo),
                  dp(i, j - 1, w_end + 1, h_end, black, memo),
                  dp(i, j - 1, w_end, h_end + 1, black, memo))
        memo[i, j, w_end, h_end, black] = res
        return res


H, W = map(int, input().split())
grid = [[None] * W for _ in range(H)]
for i in range(H):
    for j, x in enumerate(input()):
        grid[i][j] = x

memo = {}
print(min(dp(H - 1, W - 1, 0, 0, '#', memo),
          1 + dp(H - 1, W - 1, 0, 0, '.', memo)))