Partition k groups squared cost
Partition an array of non-negative integers into exactly k contiguous groups to minimize the total cost, where the cost of a group is (sum of its elements) squared. Return the minimum total cost. Constraints: 1 <= k <= length <= 2000, 0 <= each element <= 1000. The cost function is convex/monotone so the layered DP admits divide-and-conquer optimization, but a correct O(k*n^2) reference is acceptable for the bounds.
Implement
min_partition_cost(arr: list[int], k: int) → intExamples
in
[[1,2,3,4],2]out52What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 40 min
solution.py
InputExpectedGot
[[1,2,3,4],2]52not run yetsample