Coins From the Stacks

Hard

Several stacks of coins of various values lie on a table. Stack stacks[i] is listed from top to bottom: stacks[i][0] is its top coin. In one move you may take the top coin of any stack and pocket it. Make exactly picks moves so that the coins in your pocket are worth as much as possible, and return that total. A coin deep inside a stack can only be reached after every coin above it has been taken.

Example 1

stacks=[[4, 50, 2], [9, 10]], picks=2 → 54

Taking from the tops (4 + 9 = 13, or 9 + 10 = 19) loses to 4 + 50 = 54 from the first stack: to reach the 50 you first take the 4.

Example 2

stacks=[[20], [20], [1, 1, 90]], picks=3 → 92

It pays to take the whole third stack, 1 + 1 + 90 = 92, rather than both 20s and a 1 (41).

Example 3

stacks=[[7, 3]], picks=1 → 7

Constraints

1 ≤ len(stacks) ≤ 1000
1 ≤ stacks[i][j] ≤ 10⁵
Every stack is non-empty
1 ≤ picks ≤ total number of coins ≤ 2000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Prefix Sum

Similar problems

The Heaviest Reading Day Hard Merge Neighbouring Piles in Groups Hard Cutting a Berry Cake Hard Ferry Runs From the Depot Hard Merge the Front Tiles Hard

Input

stacks=[[4, 50, 2], [9, 10]], picks=2

Expected

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