Dynamic Programming Grid Traversal

HardPython

Problem

PayPal may evaluate two simultaneous paths through a grid of checkout opportunities. Two agents start in the top row, one at the leftmost column and one at the rightmost column, and move to the next row at every step.

Implement max_checkout_value(grid) to return the maximum total value both agents can collect. From column c, an agent may move to c - 1, c, or c + 1. Agents must remain inside the grid. If both agents occupy the same cell in a row, count that cell's value only once.

Formal Specification

Input: grid, a non-empty rectangular list of lists of integers, where grid[r][c] is the value at row r, column c.
Output: An integer representing the greatest total value collectable by both agents.
The first agent starts at (0, 0) and the second starts at (0, columns - 1).
Both agents must finish in the last row.

Constraints

2 <= len(grid) <= 70
2 <= len(grid[0]) <= 70
0 <= grid[r][c] <= 100
Every row has the same number of columns

Function Signature

def max_checkout_value(grid):

Formal Specification

Input: grid, a non-empty rectangular list of lists of integers, where grid[r][c] is the value at row r, column c.
Output: An integer representing the greatest total value collectable by both agents.
The first agent starts at (0, 0) and the second starts at (0, columns - 1).
Both agents must finish in the last row.