当前位置：首页 > news >正文

区间DP————石子合并

news 来源：原创 2024/5/20 22:02:16

区间DP————石子合并

合并石头的最低成本
力扣：https://leetcode-cn.com/problems/minimum-cost-to-merge-stones/
有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。
每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。
找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。

示例 1：

输入：stones = [3,2,4,1], K = 2
输出：20
解释：
从 [3, 2, 4, 1] 开始。
合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。
合并 [4, 1]，成本为 5，剩下 [5, 5]。
合并 [5, 5]，成本为 10，剩下 [10]。
总成本 20，这是可能的最小值。
示例 2：

输入：stones = [3,2,4,1], K = 3
输出：-1
解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。.
示例 3：

输入：stones = [3,5,1,2,6], K = 3
输出：25
解释：
从 [3, 5, 1, 2, 6] 开始。
合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。
合并 [3, 8, 6]，成本为 17，剩下 [17]。
总成本 25，这是可能的最小值。

提示：

1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

首先对于区间DP的一般步骤：
1、枚举所有可能的区间长度
2、枚举所有的左端点
3、枚举所有的区间分解点
4、状态转移

for( int len = 2 ; len <= n ; len++ )
{
	for( int i = 1 ; i + len - 1 <= n ; i++ )
	{
		int j = i + len - 1;
		for( int mid = i ; mid <= j ; mid++ )
		{
			//dp[i][j] = f( dp[i][j] )
		}
	}
}

本题我们可以先考虑k = 2的情况。
我们定义f[i][j]，f[i][j] 表示将第i堆石子，到第j 堆石子合并为1堆石子的最小成本,那么接下来我们考虑如何去计算f[i][j]。
由于k = 2，所以在合并任意i 到 j堆石子时，最后一定是将两堆石子合并起来，所有方案唯一的不同无非就是将i 到 j这个区间分为两个区间的分界点是哪个,所以设mid为分界点，则状态转移方程为：
f[i][j] = min( f[i][j] , f[i][mid] + f[mid+1][j] + s[j] - s[i-1] );
s为前缀和，如s[j]表示第一堆石子到第j堆石子的所有成本

那么当k 等于任意常数时该如何解决这个问题呢？

我们由简到繁，先考虑当k 为一个确定值时，什么情况下最终无法合并为一堆石子输出-1？
假设k = 3，我们直接列举可以合并为一堆的情况那就是，3堆，5堆，7堆…不难发现可以合并为一堆的情况之间都相差2，那么很容易得出公式：
当一个区间的长度(石子的堆数) = (k-1)*N + k (N=1,2,3…)时可以将所有石子合并为一堆

接着我们仍然定义状态f[i][j] ，表示将第i堆到第j堆石子合并为一堆石子的最小成本，我们还是考虑最后一步，还是假设最后是将两堆石子合并为一堆，
但两堆石子的其中一堆有 1 堆，另一堆有 k - 1 堆，这样他们一共就有k堆了，可以合并为1堆，仍然符合题意，然后这两堆又可以被划分为更小的子问题，所以
f[i][j] = min( f[i][j] , f[i][mid] + f[mid+1][j] );
在加上s[j] - s[i-1]之前要先判断一下i 到 j的区间长度是否满足 k 值

接下来是本题的代码：

#include<stdio.h>
#include<math.h>

int mergeStones(int* stones, int stonesSize, int k)
{
    int n = stonesSize;
    //若不能合并为一堆，直接返回 -1 
    if( (stonesSize-k) % (k-1) != 0 )
        return -1;
    
    int sum[n+1];
    
    //状态表示：f[i][j]：集合：所有将第 i 堆到第 j 堆石子合并为 1 堆石子的合并方法 
	//					 属性：MIN 
	//状态计算：f[i][j] = fmin( f[i][j] , f[i][mid] + f[mid+1][j] );
	//若区间长度符合要求：
	//		    f[i][j] = f[i][j] + sum[j] - sum[i-1];
    int f[n+1][n+1];
	
	//计算前缀和 
    for( int i = 1 ; i <= n ; i++ )
    {
        sum[i] = sum[i-1] + stones[i-1];
    }
	
	//初始化，仅有 f[i][j] = 0 这一个条件
    for( int i = 1 ; i <= n ; i++ )
    {
        f[i][i] = 0;
    }
	
    for( int len = 2 ; len <= n ; len++ )//枚举 区间长度 
    {
    	printf("\nlen = %d\n",len);
        for( int i = 1 ; i + len - 1 <= n ; i++ )//枚举 左端点 
        {
            int j = i + len - 1;
            f[i][j] = 1e8;//初始化初始状态为最大值，方便后续比较 
            
			//在i，j之间移动 mid ，每次移动 K-1 个距离，dp(i,mid) + dp(mid+1,j) 代表以mid为界限合并为两队的成本，取最小值 
			for( int mid = i ; mid < j ; mid += k-1 )//遍历 所有 可能的 区间分解点 
            {
                f[i][j] = fmin( f[i][j] , f[i][mid] + f[mid+1][j] );
                printf("\n判断前：i = %d ，j = %d ，f[i][j] = %d\n",i,j,f[i][j]);
            }
            if( (len-k) % (k-1) == 0 )//若区间长度可以合并,则给f[i][j]加上区间内的成本 
            {
                f[i][j] = f[i][j] + sum[j] - sum[i-1];
                printf("判断后：i = %d ，j = %d ，f[i][j] = %d\n",i,j,f[i][j]);
            }
        }
    }
    return f[1][n];//返回合并第 i 堆到第 j 堆石子的最小成本 
}

int main()
{
	int n,k;
	scanf("%d %d",&n,&k);
	
	int stones[n];
	
	for( int i = 0 ; i < n ; i++ )
	{
		scanf("%d",&stones[i]);
	}
	
	mergeStones( stones , n , k );
}