【算法】石子的合并问题（相邻和环形）_石子合并问题环形

1. 线性（相邻）合并问题

题目描述：

一条直线上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

请编辑计算出将n堆石子合并成一堆的最小得分。
Input

输入有多组测试数据。

每组第一行为n(n<=100)，表示有n堆石子，。

二行为n个用空格隔开的整数，依次表示这n堆石子的石子数量ai（0<ai<=100）

Output

每组测试数据输出有一行。输出将n堆石子合并成一堆的最小得分。

Sample Input

3

1 2 3

Sample Output

9 
1
2
3
4
5
6
7
8
9

简要概括

1. 两堆石子的得分，就是两堆石子相加的值
2. 注意，这里只能是相邻的两堆石子。加起来的可以认为是一个新的大的石子。
3. 如果要是挑出任意两个就类似与哈夫曼树，但是这里只能我们去尝试着，找出最小。

算法思想

我们利用动态规划，记录每一个状态的值，逐渐找出完整的状态。
设dp[i][j]表示第i到第j堆石子合并的最优值，sum[i][j]表示第i到第j堆石子的总数量。那么就有状态转移公式：

if( i == j)
dp[i][j] = 0;
if( i != j)    //这里我们要借助另一个变量k
{
	dp[i][j] = dp[i][k] +dp[k+1][j] + sum[i][j];       （k >= i && k < j） k不能等于 j。  因为dp[k+1]的越界。
}
1
2
3
4
5
6

其中sum[i][j]的含义是 ：第i堆到第j堆的质量和。
初始时，sum[1][1] … sum[i][i] = v[i] 。和别人合并时，比如第一堆和第二堆进行合并 sum[1][2] = sum[1][1] +sum[2][2] = v[1] + v[2]

我们维护一个len变量，代表区间长度。从【i，i + len】算出每一个最优的小区间合并石子的值。 比如石子有4个，我们可以先求出
区间为1的，【1,2】，【2,3】，【3,4】的最优小区间的合并得分。
区间为2的，【1,3】，【2,4】，（但是dp[1][3] 需要用到dp[1][2]或者dp[2][3]的值，这就是我们为什么新建一个k变量的原因）。
k变量表示的从区间起点i到区间终点，在中间怎么样分才可以使dp[i][j]可以分到最小值。

比如：
len = 1时，i = 1时， j = i+ len = 2。 此时sum[i][j]为i到j的和，k = 1时，就sum[1][2] = sum[1][1] + sum[2][2]，同时算出子结构dp[1][2]。这样下次还可以用这个dp[1][2] 作为已知变量，求出 后面的 dp[i][j] 。

代码实现

#include <iostream>
using namespace std;

int main()
{
	int n = 0;
	while (cin >> n)
	{
		vector<int> v(n + 1);
		vector<vector<int>> dp(n +1 , vector<int>(n +1, INT_MAX));
		vector<vector<int>> sum(n + 1, vector<int>(n + 1, 0));
		for (int i = 1; i <= n; i++)
		{
			cin >> v[i];
		}
		for (int i = 1; i <= n; i++)
		{
			sum[i][i] = v[i];
			dp[i][i] = 0;
		}
		for (int len = 1; len < n; len++)  // 区间长度
		{
			for (int i = 1; i + len <= n; i++)  //区间起点
			{
				int j = i + len; //区间终点
				for (int k = i; k < j; k++)
				{
					sum[i][j] = sum[i][k] + sum[k + 1][j];
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j]);
				}
			}
		}
		cout << dp[1][n] << endl;

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2. 环形合并问题

题目描述：

在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
对于给定n堆石子,计算合并成一堆的最小得分和最大得分。
Input
输入数据的第1行是正整数n，1≤n≤100，表示有n堆石子。第二行有n个数，分别表示每堆石子的个数。
Output
输出数据有两行，第1行中的数是最小得分，第2行中的数是最大得分。

Sample Input
4
4 4 5 9
Sample Output
43
54
1
2
3
4
5
6

简要概括

1. 与上面的线性相比，其实就是多加了n-1个长度。头和尾也能连接。

算法思想：（以得分最大举例）

如果将环形转换为直线
其核心思想就是：通过将数量变为 2n来转换成直线问题。 比如 数组v【1,2,3,4】，但是题目中的要求是1也可以和4连上，所以我们可以把数组v当成 【1,2,3,4,1,2,3,4】。这样子的话，我们就可以算出 【2,3,4,1】的，【3,4,1,2】，【4,1,2,3】的了。

sum数组的含义： sum[i]就是从数组v[1]到数组v[i]的和。方便求后面的区间len上面 dp[i][j](从第i堆到第j堆的总数量，sum[j] - sum[i-1]）
dp数组的含义：dp[i][j] 代表从第i堆到第j堆数组的合并得分。

转移方程

if( i == j)
dp[i][j] = 0;
if( i != j)    //这里我们要借助另一个变量k
{
	dp[i][j] = dp[i][k] +dp[k+1][j] + sum[j] - sum[i-1];  （k >= i && k < j） 这里原来的的sum[i][j] 要被替换为 sum[j] - sum[i-1]。  
}
1
2
3
4
5
6

sum[j] - sum[i-1] ,就是求出第i堆 到第j堆的 所有堆之和。


初始的时候： 
1. dp[i][i] = 0。因为从第i堆到第i堆不用合并，所以得分为0
2. sum[i] = v[1] + ... v[i] 。所以sum[i] = sum[i-1] + v[i]
##### 代码实现：
```cpp
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int n = 0;
	cin >> n;

	vector<int> v(2*n + 1);      // 
	vector<int> sum(2 * n + 1);  // 创建sum数组，记录的是从 v[1]到v[i]的和
	vector<vector<int>> dp(2*n + 1, vector<int>(2*n + 1, INT_MIN));

	for (int i = 1; i <= n; i++)
	{
		cin >> v[i];
	}
	for (int i = n + 1; i <= 2 * n; i++)
	{
		v[i] = v[i - n];
	}

	for (int i = 1; i <= 2 * n; i++)
	{
		sum[i] = sum[i - 1] + v[i];
		dp[i][i] = 0;
	}

	for (int len = 1; len < n; len++) //枚举区间长度
	{
		for (int i = 1; i + len < 2 * n; i++) 
		                                // 枚举区间的起始位置 （a b c a b c） i <= 3就好了,也就是 i+len<2*n 
		{							    //                    1 2 3
			int j = i + len; // 最后位置
	
			for (int k = i; k < j; k++)
			{
				dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + (sum[j] - sum[i - 1])); //和线性的一致
			}
		}
	}

	int max_ = 0;
	for (int i = 1; i <= n; i++)  //看从哪一个 i开始 到 i+n-1 是最大的
	{
		max_ = max(dp[i][i + n - 1], max_);
	}

	cout << max_ << endl;
	system("pause");

	//最后一步求 max_
	//    例如 :          a b c a b c
	//		         1.   a b c
	//				 2.		b c a
    //               3.       c a b
	//    看以 1，2,3 哪一个开始是最大的
	//
	//
	
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70