区间dp（入门）

这个区间dp学完dp就先告一段落了。虽然感觉dp还是啥都不会吧，但是比以前强了那么一点点，至少现在听见那希望名字知道是干什么用的了，这次我们简单的说一下区间dp。

顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。

既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。
 

这也算是小暴力吧，首先我们要枚举区间的长度，然后枚举区间的开始点，然后再枚举这个区间的分割点，三个for嵌套，就行了，

下面给一个例题。

石子合并

这个题的大致意思就是给你一堆的石子，然后你要把这些合并成一堆石子，每次合成的代价是两堆所有的石子之和

下面给出AC代码.并附上详细的注释，

#include
using namespace std;
const int maxn=1003;
const int INF=0x3f3f3f;
int a[maxn];
int dp[maxn][maxn];//dp[i][j] i表示这个区间的起点，j表示这个区间的终点
int sum[maxn];
int main()
{int n;scanf("%d",&n);memset(sum,0,sizeof(sum));memset(dp,INF,sizeof(dp));//对dp进行初始化，因为要求最小值，所以初始化为最大for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];dp[i][i]=0;}for(int len=2;len<=n;len++)//枚举长度{for(int i=1;i<=n-len+1;i++)//枚举起点{int end1=i+len-1;for(int j=i;j

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！