Solution to http://100.70.19.162:8000/contest/32/12

help_the_robot.py

import sys

"""
  Solution to http://100.70.19.162:8000/contest/32/12
"""

# input handling
maze = sys.stdin.read().splitlines()
height, width = int(maze.pop(0)), int(maze.pop(0))

# sanitize maze
maze = [list(map(int, row.split(' '))) for row in maze]

# reverse columns so bottom left is 0,0
maze.reverse()

# initialize cache representing stored optimal values at each location
cache = [[None for _ in range(width)] for _ in range(height)]

# bottom up dp
def max_coins(x, y):
    global maze
    global cache

    if x < 0 or y < 0:
        return 0
    if cache[y][x] is not None:
        return cache[y][x]
    cache[y][x] = maze[y][x] + max(max_coins(x - 1, y), max_coins(x, y - 1))
    
    return cache[y][x]

print(max_coins(width - 1, height - 1))