首页 / 更多教程 / DP经典题型：石子合并问题
DP经典题型：石子合并问题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了DP经典题型：石子合并问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1750字，纯文字阅读大概需要3分钟。
内容图文
本周集训专题为DP系列，一个经典的系列便是石子归并问题。
(1)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。
这是石子归并的简化版本，石子处于一排。由于发现只能是相邻的2堆石子进行归并。我们会发现，贪心算法在此处便失去作用，局部最优解并不能带来整体最优解。
因此，不难让我们想到，此题应该采取DP(dynamic Programing)来求其最优解。
动态规划常常采取从部分整体最优解的拆分来得到最优解法的递归式，我们可以想到，此处是由2堆石子合并，所以最终最优解肯定是由两个局部最优解的加上整体的和求得。
因此，我们可以推断出动态转移方程：
dp[i][j]在此处表示从第i堆加到第j堆的最优解，而当i == j是，并不存在相加，所以结果为0.
(2)将上述问题从一排改为环形，便是完整版本的石子合并问题了。
不难发现，其实解法类似。不过由于是环形，我们要在每次相加只有都对个数取余数，以防止数组越界。
不过，此处的j与前面(1)中的j意义并不一样，此处的j意义为：从第i堆出发，往下数j堆石子。因此，j == 0时，自然dp[i][j] == 0了
因为j的意义不同，所以dp[i][j]长得自然不一样了，实际上还是一个意思。
所以sum[i][j]也改为：
附上求最小值的代码：
1 #include <iostream>
2 #include <algorithm>
3 #include <limits>
4usingnamespace std;
5constint INF = INT_MAX;
6constint maxn = 1003;
7int dp[maxn][maxn];
8int stone[maxn];
9int sum[maxn]; //0 - i 的和10int n; //本次的个数11int getSum(int i, int j) {
12if (i + j >= n)
13return getSum(i, n - i - 1) + getSum(0, i + j - n);
14else15return sum[i + j] - (i > 0 ? sum[i - 1] : 0);
16}
17int findMin() {
18for (int i = 0; i < n; i++) {
19 dp[i][0] = 0;
20 }
21for (int j = 1; j < n; j++) {
22for (int i = 0; i < n; i++) {
23 dp[i][j] = INF;
2425for (int k = 0; k < j; k++) {
26 dp[i][j] = min(dp[i][j], dp[i][k] + dp[(i + k + 1) % n][j - k - 1] + getSum(i, j));
27 }
28 }
29 }
30return dp[0][n - 1];
31}
3233int main() {
34while (cin >> n) {
35for (int i = 0; i < n; i++) {
36 cin >> stone[i];
37 sum[i] = 0;
38 }
39 sum[0] = stone[0];
40for (int i = 1; i < n; i++) {
41 sum[i] = sum[i - 1] + stone[i];
42 }
43 cout << findMin() << endl;
44 }
45return0;
46 }
Vane_Tse On the Road. 2014-07-10 10:04:43
原文：http://www.cnblogs.com/slimjerk/p/3835131.html
内容总结
以上是互联网集市为您收集整理的DP经典题型：石子合并问题全部内容，希望文章能够帮你解决DP经典题型：石子合并问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。