动态规划之区间DP

原创

王脸小

修改于 2019-12-09 14:39:26

4130

修改于 2019-12-09 14:39:26

文章被收录于专栏：王漂亮王漂亮

区间dp入门——总结+习题+解析

区间dp，顾名思义，在区间上dp，大多数题目的状态都是由区间（类似于dp[l][r]这种形式）构成的，就是我们可以把大区间转化成小区间来处理，然后对小区间处理后再回溯的求出大区间的值，主要的方法有两种，记忆化搜索和递推。

1000. 石头合并

Minimum Cost to Merge Stones

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

[Java/C++/Python] DP

Python, DP, easy to understand

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 删除。

python

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

python

登录后参与评论

0 条评论

热度