区间dp,顾名思义,在区间上dp,大多数题目的状态都是由区间(类似于dp[l][r]这种形式)构成的,就是我们可以把大区间转化成小区间来处理,然后对小区间处理后再回溯的求出大区间的值,主要的方法有两种,记忆化搜索和递推。
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.
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.
Solution
import functools
class Solution:
def mergeStones(self, stones, K):
prefix = [0] * (len(stones) + 1)
for i in range(len(stones)):
prefix[i + 1] = prefix[i] + stones[i]
@functools.lru_cache(None)
def dp(i, j, m):
if (j - i + 1 - m) % (K - 1):
return -1
if i == j:
return 0 if m == 1 else -1
if m == 1:
return dp(i, j, K) + prefix[j + 1] - prefix[i]
return min(dp(i, mid, 1) + dp(mid + 1, j, m - 1) for mid in range(i, j, K - 1))
res = dp(0, len(stones) - 1, 1)
return res
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。