石子合并问题是一个经典的动态规划问题，应用了最优子结构和重复子问题的思想。
有如下3种题型：
不加限制的合并
(1)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成
(动态规划)O(n^3)
设dp[i][j]表示将i至j之间的石子合并成一堆的最小花费。
初始时，对于任意i，都有dp[i][i]=0，因为合并一堆石子不需要花费。
对于区间[i,j]，枚举合并点k，则该区间合并的最小花费为: dp[i][k]+ dp[k＋1][j]＋sum[i][j]，其中 sum[i][j]表示区间[i,j]中石子数量的和。最终答案即为dp[1][n]。
线性（相邻）合并问题
(2)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。
具体思路如下：
-
确定状态
设dp[i][j]表示合并第i到j个石子的最小代价。
2.确定状态转移方程
对于第i到第j个石子的合并，可以选择在任意一个位置k断开，将问题分成合并i到k之间的石子和合并k+1到j之间的石子两个子问题。
因此，可以得到状态转移方程：
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[i][j]) (i <= k < j)
其中sum[i][j]表示第i到第j个石子的重量和，即需要合并的代价。
3.确定边界
当只有一个石子时，代价为0，因此dp[i][i] = 0。
4.最终结果
最终的结果为dp[1][n]，表示合并全部石子的最小代价。
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]);
}
}
}我的代码
我在下面的代码中，对sum数组进行了优化（前缀和优化），用s数组表示
#include <iostream>
#include <cstring>
using namespace std;
const int N = 310;
int n;
int a[N], s[N]; // s数组用于前缀和优化
int f[N][N]; // f[i][j]表示合并第i~j堆石子的最小代价
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ )
cin >> a[i];
// 前缀和优化
for (int i = 1; i <= n; i ++ )
s[i] = s[i - 1] + a[i];
memset(f, 0x3f, sizeof f); // 初值无穷大
for (int i = 1; i <= n; i ++ )
f[i][i] = 0; // 一堆石子不需要合并
// 枚举区间长度
for (int len = 2; len <= n; len ++ )
{
// 枚举区间起点
for (int i = 1; i + len - 1 <= n; i ++ )
{
int j = i + len - 1; // 区间终点
// 枚举划分位置
for (int k = i; k < j; k ++ )
{
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}
}
cout << f[1][n] << endl;
return 0;
}环形合并
(3)问题(2)的是在石子排列是直线情况下的解法，如果把石子改为环形排列，又怎么做呢？
核心思想：
将环形转换为直线
通过将数量变为 2n来转换成直线问题。 比如数组a【1,2,3】，但是环形的要求是1也可以和3连上，所以我们可以把数组a当成 【1,2,3,1,2,3】。这样，我们就可以算出 【2,3,1】的，【3,1,2】的。文章来源：https://www.toymoban.com/news/detail-461954.html
我的代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 310;
int n;
int a[2*N+1], s[2*N+1]; // s数组用于前缀和优化
int f[2*N+1][2*N+1]; // f[i][j]表示合并第i~j堆石子的最小代价
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ )
cin >> a[i];
for (int i = n + 1; i <= 2 * n; i++)
a[i] = a[i - n];
// 前缀和优化
for (int i = 1; i <= 2 * n; i ++ )
s[i] = s[i - 1] + a[i];
memset(f, 0x3f, sizeof f); // 初值无穷大
for (int i = 1; i <= 2 * n; i ++ )
f[i][i] = 0; // 一堆石子不需要合并
// 枚举区间长度
for (int len = 2; len <= n; len ++ )
{
// 枚举区间起点
for (int i = 1; i + len - 1 <= 2 * n; i ++ )
{
int j = i + len - 1; // 区间终点
// 枚举划分位置
for (int k = i; k < j; k ++ )
{
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}
}
cout << f[1][n] << endl;
return 0;
}通过上述的状态转移方程，可以将问题分解成两个子问题，并且可以通过最优子结构来推导出最终的结果。同时，由于每个子问题都有重复的子问题，因此可以通过动态规划算法来避免重复计算，提高算法效率。文章来源地址https://www.toymoban.com/news/detail-461954.html
到了这里，关于石子合并问题（动态规划）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
