Asked at

Last Stone Weight II

Hard
VerifiedArrayDynamic ProgrammingKnapsack~30 min

Each turn, smash two stones; the difference (or zero) returns to the pile. Pick smashes to minimize the final stone’s weight. This reduces to splitting stones into two groups with the smallest possible sum difference.

The input arrives as a single array stones. Return the smallest possible final weight.

Examples

in[2, 7, 4, 1, 8, 1]
out1

Optimal smashing leaves a stone of weight 1.

in[31, 26, 33, 21, 40]
out5

Split into near-equal sums; the gap is 5.

Constraints

  • 1 ≤ stones.length ≤ 30
  • 1 ≤ stones[i] ≤ 100
  • Target: O(n · sum) time

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.