Hopping Down the Rows

Medium

You are given a field field with m rows and n columns that contains every number from 0 to m·n − 1 exactly once. You start in any cell of the top row and go down: from a cell in row r you may jump to any cell of row r + 1. Jumping from the cell holding value v to column d of the next row costs hop_cost[v][d]. The cost of a path is the sum of the values of all visited cells plus the cost of all jumps. The path ends in any cell of the bottom row. Return the lowest possible cost of such a path.

Example 1

field=[[2, 0], [1, 3]], hop_cost=[[6, 2], [4, 9], [1, 7], [5, 5]] → 4

Path 2 → 1 costs 2 + 1 for the cells plus 1 for the hop from 2 to column 0, so 4 in total. The next best, 0 → 3, costs 0 + 3 + 2 = 5.

Example 2

field=[[3, 4, 0], [1, 5, 2]], hop_cost=[[8, 9, 7], [1, 1, 1], [1, 1, 1], [2, 6, 3], [10, 1, 10], [1, 1, 1]] → 6

The best is 3 → 1: 3 + 1 for the cells plus 2 for the hop, 6 in total.

Example 3

field=[[1, 0], [2, 3], [5, 4]], hop_cost=[[3, 3], [1, 2], [2, 2], [4, 1], [1, 1], [1, 1]] → 10

Constraints

2 ≤ m, n ≤ 50
field contains every number from 0 to m·n − 1 exactly once
len(hop_cost) = m·n, len(hop_cost[v]) = n
1 ≤ hop_cost[v][d] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Matrix

Similar problems

Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium Largest Solid Square Medium Best Spot for the Turret Medium Steps to the Nearest Zero Medium

Input

field=[[2, 0], [1, 3]], hop_cost=[[6, 2], [4, 9], [1, 7], [5, 5]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 6 tests on the server, hidden ones included.