Description
There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.
A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.
Find the minimum cost to merge all piles of stones into one pile. If it is impossible, return-1.
有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。
每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。
找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。
题目链接：https://leetcode.com/problems/minimum-cost-to-merge-stones/
Difficulty: hard
Example 1:
Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation:
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.
Example 2:
Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore. So the task is impossible.
Example 3:
Input: stones = [3,5,1,2,6], K = 3
Output: 25
Explanation:
We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.
Note:
- 1 <= stones.length <= 30
- 2 <= K <= 30
- 1 <= stones[i] <= 100
分析
- prefix[i]代表前i堆石头的总数，dp(i,j)代表把第i堆到第j堆合并成一堆的成本；
- 在i，j之间移动mid，每次移动K-1个距离，dp(i,mid)+dp(mid+1,j)代表以mid为界限合并为两队的成本，取最小值；
- 若(j - i) % (K - 1)==0即可以合并为一堆，res再加上两堆的石头数（prefix[j+1]-prefix[i]）
- dp(i,j)返回res；
- 若n堆不能合并成一堆（(n-1)%(K-1)不等于0），返回-1；
- 反之返回dp(0,n-1)
参考代码
def mergeStones(self, stones, K):
n = len(stones)
if (n - 1) % (K - 1): return -1
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + stones[i]
import functools
@functools.lru_cache(None)
def dp(i, j):
if j - i + 1 < K: return 0
res = min(dp(i, mid) + dp(mid + 1, j) for mid in range(i, j, K - 1))
if (j - i) % (K - 1) == 0:
res += prefix[j + 1] - prefix[i]
return res
return dp(0, n - 1)