How should I practice Minimum Cost to Merge Stones?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen and onsite interview problems in FastPrep.

Is Minimum Cost to Merge Stones associated with Google?

FastPrep tags this as a Google phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

Minimum Cost to Merge Stones

Google● HardINTERNNEW GRADPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

You are given an array stones, where stones[i] is the number of stones in pile i, and an integer k.

In one move, choose exactly k consecutive piles and merge them into one pile. The cost of the move is the total number of stones in those k piles.

Return the minimum total cost needed to merge all piles into one pile. Return -1 if it is impossible.

Function

mergeStones(stones: int[], k: int) → int

Examples

Example 1

stones = [3,2,4,1]k = 2return = 20

One optimal sequence is [3,2,4,1] -> [5,4,1] -> [5,5] -> [10], with total cost 5 + 5 + 10 = 20.

Example 2

stones = [3,2,4,1]k = 3return = -1

Each move reduces the number of piles by two, so four piles cannot become exactly one pile.

Example 3

stones = [3,5,1,2,6]k = 3return = 25

Merge [5,1,2] for cost 8, then merge [3,8,6] for cost 17.

Constraints

1 <= stones.length <= 30.
1 <= stones[i] <= 100.
2 <= k <= 30.