动态规划之石子合并

1、问题

( 1 )路边玩法
有 n 堆石子堆放在路边,现要将石子有序地合并成一堆,规定每次只能移动相邻的两堆石子合并,合并花费为新合成的一堆石子的数量。求将这 N 堆石子合并成一堆的总花费(最小或最大)。

2、分析

( 1 )建立最优值递归式
设 Min [i][j] 代表从第 i 堆石子到第 j 堆石子合并的最小花费, Min [i][k] 代表从第 i 堆石子到第 k 堆石子合并的最小花费,Min[k+1][j] 代表从第 k+1 堆石子到第 j 堆石子合并的最小花费, w ( i , j )代表从 i 堆到 j 堆的石子数量之和。列出递归式:
Min [ i ][ j ] = 0 （i = j）
Min [ i ][ j ] = min ( Min [ i ][ k ] + Min [ k + 1][ j ] + w ( i , j )) , i < j（ i ≤ k < j）
Max [i][j] 代表从第 i 堆石子到第 j 堆石子合并的最大花费,Max [i][k] 代表从第 i 堆
石子到第 k 堆石子合并的最大花费,Max [k+1][j] 代表从第 k+1 堆石子到第 j 堆石子合并的最大花费, w ( i , j )代表从 i 堆到 j 堆的石子数量之和。列出递归式:

Max [ i ][ j ] = 0 （i = j）
Max [ i ][ j ] =max( Max [ i ][ k ] + Max [ k + 1][ j ] + w ( i , j )) , i < j （ i ≤ k < j）

二维数组 Min [i][j] 、Max [i][j] 来记录第 i 堆到第 j 堆 a i , a i+1 ,..., a i 堆石子合并的最小花费和最大花费。
( 2 )初始化
输入石子的堆数 n ,然后依次输入各堆石子的数量存储在 a[i] 中,令 Min [i][i]=0 ,
Max [i][i]=0 , sum[0]=0 ,计算 sum[i] ,其中 i= 1 , 2 , 3 ,..., n 。
( 3 )循环阶段
• 按照递归式计算 2 堆石子合并 {a i , a i+1 } 的最小花费和最大花费, i=1 , 2 , 3 ,..., n−1 。
• 按照递归式计算 3 堆石子合并 {a i , a i+1 , a i+2 } 的最小花费和最大花费, i=1 , 2 , 3 ,...,n−2 。
•

以此类推,直到求出所有堆 {a 1 ,..., a n } 的最小花费和最大花费。

3、代码实现

#include <iostream>

using namespace std;

#define LEN 1024
#define MAXDATA 200000
int MIN[LEN][LEN];
int MAX[LEN][LEN];
int data[LEN];
int sum[LEN];

int min(int a, int b)
{
	return a > b? b : a;
}

int max(int a, int b)
{
	return a > b ? a : b;	
}

void straight(int len)
{
	//初始化对角线,我们知道MIN[i][i]和MAX[i][i]为0
	for (int i = 1; i <= len; ++i)
	{
		MIN[i][i] = 0;
		MAX[i][i] = 0;
	}
	sum[0] = 0;
	sum[1] = data[1];
	for (int i = 1; i < len; ++i)
	{
		sum[i + 1] = sum[i] + data[i + 1];
	}
	for (int i = 0; i <= len; ++i)
	{
		std::cout << sum[i] << "\t";
	}
	//数据坐标分析,我们知道是需要循环5次
	for (int v = 2; v <= len; ++v)
	{
    /** 
	下面是其中的下标的数据,我们知道i从1到5,1到4,1到3,1到2,1到1,
	j从2到6,3到6,4到6,5到6,6到6
	1,2 1,3 1,4 1,5 1,6
	2,3 2,4 2,5 2,6
	3,4 3,5 3,6
	4,5 4,6
	5,6
	**/
		for (int i = 1; i <= len - v + 1; ++i)
		{
			int j = i + v - 1;
			MIN[i][j] = MAXDATA;
			MAX[i][j] = -1;
			int temp = sum[j] - sum[i - 1];
			for (int k = i; k < j; ++k) 
			{
				MIN[i][j] = min(MIN[i][j], MIN[i][k] + MIN[k + 1][j] + temp);
				MAX[i][j] = max(MAX[i][j], MAX[i][k] + MAX[k + 1][j] + temp);
			}
		}
	}
}


int main()
{
	int all;
	std::cout << "请输入有多少堆石子" << std::endl;
	std::cin >> all;
	std::cout << "请分别输入每堆石子的个数" << std::endl;
	for (int i = 1; i <= all; ++i)
	{
		std::cin >> data[i];
	}
	straight(all);
	std::cout << "\n";
	std::cout << "直线形最小花费是" << MIN[1][all] << std::endl;
	std::cout << "直线形最大花费是" << MAX[1][all] << std::endl;
	return 0;	
}

4、运行结果

请输入有多少堆石子
6
请分别输入每堆石子的个数
3
4
3
34
3
3
0	3	7	10	44	47	50	
直线形最小花费是113
直线形最大花费是219

5、总结

循环的时候我们要知道斜着有5斜杠，所以是5次循环，然后分析i,每次结尾不同，开始一样，然后再找出j的关系，然后每次初始化最大值和最小值，然后每次通过min函数进行每次把MIN[i][j]把自己传递进去和k一次增加的MIN[i][ k] + MIN[K+1][j] + temp进行对比，因为 MIN[i][j]每次保存在数组里面，所以每次都有记录才可以这样循环比，得到最小的和最大的

时间复杂度最坏0(n3)