Leetcode 1000. Minimum Cost to Merge Stones | 区间dp | 石子归并

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.

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

Analysis

有N堆石头排列成一行,每次我们可以将连续的k堆石头进行合并,合并的cost等于这k堆石头的石头个数,求合并成一堆的最小cost。

题意是合并连续的k堆,In a simple way,我们先看一下k=2的情况

当k=2时,题目变成了一道经典的区间dp的问题。

区间dp以区间作为动态规划过程中的状态。有如下模板代码:

for(int i=1; i<=n; i++)
{
  dp[i][i]=初始值
}

for (int len = 2; len <= n; len++) { // len代表区间中一共有几个点
  for (int i = 1; i <= n; i++) { // 枚举起点
    int j = i + len - 1; // 计算终点
    if (j > n) continue;
    for (int k = i; k < j; k++) { // 枚举分割点,构造状态转移方程
      dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
    }
  }
}

对于上述模板代码,我们需要明确几个点:

  1. dp[i][j]代表cover第i个数到第j个数的区间。
  2. len代表区间中一共包含几个点,初始值为2
  3. k代表分割点,k处于左闭右开的区间,因为我们分割的时候是分割成两个闭区间。

好了,当我们对于区间dp的模板有了一个了解后,石子归并k=2的代码就可以写出来了。代码如下:

class Solution {
    public int mergeStones(int[] stones, int K) {
        int n = stones.length;
        int[][] dp = new int[n + 1][n + 1];
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = stones[i - 1] + sum[i - 1];
        }
        // dp[i][i]本身就代表一pile,因此cost为0
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) { // j <= n可以推导出i的更精确范围
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE; // 初始化为最大值,且i绝不会等于j
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
                }
            }
        }
        return dp[1][n];
    }
}

此时时间复杂度为O(n3)。

回到题意,现在我们需要解当k不等于2的问题。

为了让我们的dp数组中保存有目前有多少堆信息,我们需要给它升成3维。

令dp[i][j][m] 代表将第i个数到第j个数的区间合并成m堆。

初始化
dp[i][i][1] = 0, dp[i][i][m] = Integer.MAX_VALUE.  // 因为我们是求最小,那么无效值就设置最大值

转移方程
dp[i][j][1] = dp[i][j][K] + sum(i, j) // 按照题意我们可以将连续的K堆合并成1堆。
dp[i][j][m] = min(dp[i][mid][1] + dp[mid + 1][j][m - 1])

得到如下代码:

class Solution {
    public int mergeStones(int[] stones, int K) {
        int n = stones.length;
        if ((n - 1) % (K - 1) != 0) {
            return -1;
        }
        int[][][] dp = new int[n + 1][n + 1][K + 1];
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = stones[i - 1] + sum[i - 1];
        }
        int max = 999999;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= K; k++) {
                    dp[i][j][k] = max;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            dp[i][i][1] = 0;
        }


        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                for (int k = 2; k <= K; k++) {
                    for (int mid = i; mid < j; mid++) {
                        dp[i][j][k] = Math.min(dp[i][j][k], dp[i][mid][k-1] + dp[mid + 1][j][1]);
                    }
                }
                dp[i][j][1] = dp[i][j][K] + sum[j] - sum[i - 1];
            }
        }
        return dp[1][n][1];
    }
}

注意这里的最大值用的999999,因为用Integer.MAX_VALUE的时候在加法似乎存在越界的情况。这个挺坑的,以后不能想当然的都用Integer.MAX_VALUE了,最好根据题目的取值范围设置。

解到这里,这道题目还没完。在DISCUSS里面看了lee神的解法,原来3维可以优化成两维。

Solution

对于m堆石头我们至多只能将其合并成(j - i) % (K - 1) + 1堆,它必定小于K堆。

Java: Time O(N^3/K), Space O(N^2)

    public int mergeStones(int[] stones, int K) {
        int n = stones.length;
        if ((n - 1) % (K - 1) > 0) return -1;

        int[] prefix = new int[n+1];
        for (int i = 0; i <  n; i++)
            prefix[i + 1] = prefix[i] + stones[i];

        int[][] dp = new int[n][n];
        for (int m = K; m <= n; ++m)
            for (int i = 0; i + m <= n; ++i) {
                int j = i + m - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int mid = i; mid < j; mid += K - 1)
                    dp[i][j] = Math.min(dp[i][j], dp[i][mid] + dp[mid + 1][j]);
                if ((j - i) % (K - 1) == 0)
                    dp[i][j] += prefix[j + 1] - prefix[i];
            }
        return dp[0][n - 1];
    }

Conclusion

hard常作为follow-up,一般来讲我们可能无法想出follow-up的解法,但是基本的区间dp模板还是要会套的。

2 条评论

  • 动态规划之平行四边形优化 – Yuxiang's Blog 2020年3月15日 回复

    […] 推荐阅读:区间dp – 石子归并 […]

  • 环形石子归并问题 – Yuxiang's Blog 2020年3月18日 回复

    […] 这是之前的石子归并k=2的情况下的变体。石子是按照环形排布的。 […]

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号