石子归并---区间型动态规划

本文主要是介绍石子归并---区间型动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述 Description

有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。

输入描述 Input Description

第一行一个整数n（n<=100）

第二行n个整数w1,w2...wn  (wi <= 100)

输出描述 Output Description

一个整数表示最小合并代价

样例输入 Sample Input

4

4 1 1 4

样例输出 Sample Output

18

数据范围及提示 Data Size & Hint

本题的解法是在codevs上的题解中看到的，现在借鉴一下，感觉非常不错。

对于区间DP的问题，我们可以采用记忆化搜索的形式，也可以采取递推的形式。。但两者的实质是一样的。。

我们可以把石子的合并问题转化为对与区间的划分问题，从而建立数学模型。。石子合并问题也就转换成了区间划分代价最小的问题。。

注意点是在用记忆化搜索写的时候要进行适当的初始化，并且注意区间划分不要出现无穷递归的情形，选好划分点。

递推形式写的时候相当于枚举区间的长度，然后对区间的划分点进行枚举。。两种方法的实质相同。。希望两种方法都能学会并熟练掌握。

 

递推法：

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[105];
int sum[105];
int d[105][105];
const int INF = (1 << 30);
int main(){int n, i;scanf("%d", &n);for (i = 1; i <= n; i++){scanf("%d", &a[i]);sum[i] = sum[i - 1] + a[i];}int len, j, k;for (len = 1; len < n; len++){for (i = 1; i <= n - len; i++){int res = INF;j = i + len;for (k = i; k < j; k++)res = min(res, d[i][k] + d[k + 1][j] + sum[j] - sum[i - 1]);d[i][j] = res;}}printf("%d\n", d[1][n]);return 0;
}

递推就是把所有可能出现的情况都枚举一遍，然后线性扫描，找到代价最小的。

 

下面是记忆化搜索， 相比递推比较容易理解

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[110];
int sum[110];
int dp[110][110];
const int INF = (1 << 30);
int solve(int l, int r)
{if (dp[l][r] != -1)return dp[l][r];int res = INF;for (int i = l; i <= r - 1; i++)res = min(res, solve(l, i) + solve(i + 1, r) + sum[r] - sum[l - 1]);return dp[l][r] = res;
}
int main()
{int n;scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d", &a[i]);sum[i] = sum[i - 1] + a[i];}memset(dp, -1, sizeof(dp));for (int i = 1; i <= n; i++)    //注意要初始化为0dp[i][i] = 0;printf("%d\n", solve(1, n));return 0;
}

公众号「后知后jue」，微信搜索关注回复「1024」，你懂的！

这篇关于石子归并---区间型动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---