今天就进入新的篇章了：区间dp

目录

  区间dp简述

            模板：

 题目：石子合并

   思路： 

 题目：租界游艇

   思路： 

 题目：

   思路：

---

  

    

区间dp简述：

概述：
区间dp：就是对于区间的一种动态规划，对于某个区间，它的合并方式可能有很多种，我们需要去枚举所有的方式，通常是去枚举区间的分割点，找到最优的方式(一般是找最少消耗)。

例如：对于区间【i，j】，它的合并方式有很多种，可以是【i，i+1】和【i+2，j】也可以是【i，k】和【k+1，j】（其中i <= k < j）……

在合并区间时，一般会有消耗，状态转移方程可以表示成：

dp[i][j] = min(dp[i][j], dp[i,k] + dp[k+1][j] + 合并区间的消耗 ) （k是区间分割点）

你会发现区间dp的本质就是把所有的区间都处理一遍，无非把遍历顺序是从(1,2)(1,3)(1,4)(1,5)……(2,3)(2,4)(2,5)……变成了(1,2)(2,3)(3,4)(4,5)……(1,3)(2,4)(3,5)……懂了吗

  

模板：

通常都是先枚举区间长度，区间长度为1就不用合并，所以从2开始枚举，然后枚举左端点，那么右端点就为左端点加区间长度-1，再枚举分割点 k，最后计算不同分割点 k 的情况下，合并区间的消耗，dp[i][j]选择其中的最小消耗。

  （有点像快速幂，都是从小变大嘛）

for(int len=2;len<=n;len++)//先枚举区间长度
  for(int i=1;i<=n-len+1;i++){//再枚举区间左端点，左端点加区间长度为右端点，不能大于n
     int j=i+len-1;//区间右端点
     for(int k=i;k<j;k++)//枚举区间分割点，注意k不能取j，不理解你就带入就知道了
         dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+合并区间的消耗);
}

   

    

 上正题了

 题目：石子合并

  

     

思路： 

我知道这个题当你没有了解过区间dp的时候，第一个会很容易想到贪心，然后优先队列优化。不过你仔细看看，好像不是哦~ 你看题上的条件是合并相邻的，不是自由合并的！所以这是一道裸的区间dp题

状态设置：dp[i][j]表示第i堆到第j堆合并后对应的最小代价，先去更新最小的区间，然后dp[i][j]可以由小的区间长度进行转移

注意初始化问题：你要的是最小值，那就要初始化成INF；端点初始化成本身。

还有要注意的是本题中的代价是会在合并时候发生变化，所以你要尽可能快的去求出代价！

#include<bits/stdc++.h>    
using namespace std;    //区间dp
int dp[310][310],len,a[310],n,sum[310];
int main()
{
	cin>>n;
	memset(dp,0x3f,sizeof(dp));//初始化1，因为是求最小代价，所以初始化设为很大的一个数，为了后面更新。
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		dp[i][i]=0;//初始化2，他自己本身的代价为0。
	}
	for(int len=2;len<=n;len++) //每个区间长度都遍历，方便下个长度区间使用
		for(int i=1;i<=n-len+1;i++){//从1下标开始遍历每个起点
			int j=i+len-1;
			for(int k=i;k<j;k++){//每个区间进行取优，枚举每个分割点，可以取i，不要取j
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
			}
		}
	cout<<dp[1][n];
}

  

---

   

 题目：租界游艇

   

  

思路： 

你如果你完全是个小白的话，可能没有任何思路，只会想到dfs；但是当你有了一点点算法沉淀后，你会不自觉地有种想想跑图的冲动！哈哈哈哈，完全可以的，数据范围并不是特别大，你用优化的dijkstra，floyd，spfa算法都是可以跑的。这里说一下注意事项：这道题是有向图，怎么跑最短路随你，但是题意别理解错了。（有些人看不懂这里就当我啥也没说，以后会讲） 

其实你看到“半矩阵”时候，应该就知道区间dp其实也是可以的。然后套模板就行了 

      

#include <bits/stdc++.h>//P1359：一共有n个游艇出租站，所有的站间都会有R租金,问从1到n所需要的最少租金？(其实应该是完全有向图，如果跑图的话)
using namespace std;
int dp[205][205],s[205][205],n;
void print(int i,int j){//输出具体路径算法
	if(s[i][j]==0){cout<<"--"<<j;return ;
	}
	print(i,s[i][j]);//i必须先递归
	print(s[i][j],j);
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++)
	for(int j=i+1;j<=n;j++){
		cin>>dp[i][j];
	}
	for(int d=3;d<=n;d++){//区间长度
		for(int i=1;i<=n-d+1;i++){//左端点
			int j=i+d-1;//右端点
			for(int k=i+1;k<j;k++){//引入中间点
				if(dp[i][j]>dp[i][k]+dp[k][j]){
					dp[i][j]=dp[i][k]+dp[k][j];
					s[i][j]=k;//这步和题没关系
				}
			}
		}
	}
	//print(1,n);//之所以写个这函数，是为了给你看看具体的最短路径
	cout<<dp[1][n];
}

     

---

    

  最后再来道我最想说的题吧：

 题目：？？？

  

（是atcoder比赛遇到的一道题，感觉出的挺好的所以拿出来）我给你总结一下题意：

一个长为n且仅由0~9组成的字符串数num，对其中某一子串进行翻转得num2，若num2<num（这里是比较字符串的大小）则方案成立(我们允许num2以0开始)，问一共有多少种方案？ （n<=5000）

  

思路：

很明显，要在O(n^2)内完成本题，但是判断每种方案是否满足又是一件头疼的事情，只能在O(n)内完成。

  
那么可以定义dp[i][j]表示从i下标到j下标的方案是否合法，主要就是为了快速求dp[i][j]

当我们在判断dp[i][j]是否合法时，完全可以借助之前的结果

最后把所有的合法的种类加起来就行了

  
如果字符s[i]>s[j]  则dp[i][j]=1（合法）
如果s[i]==s[j] 则dp[i][j]=dp[i+1][j-1]（里面的字符串是合法的则外面的也合法，否之不合法）

#include <bits/stdc++.h>
using namespace std;//只要子串的起止下标i，j不同，就认为是新的方案。              
int dp[5005][5005],ans;//dp[i][j]表示起止下标为i，j的子串方案成不成立
int main(){
	string s;cin>>s;
	int n=s.size(),r;
	for(int len=2;len<=n;len++)
	for(int l=0;l+len<=n;l++){
		r=l+len-1;
		if(s[l]>s[r])dp[l][r]=1;
		else if(s[l]==s[r])dp[l][r]=dp[l+1][r-1];//从更少的len处转移
		ans+=dp[l][r];
	}
	cout<<ans;
}

 呼~ 终于讲完了。累死我了，点个赞再走吧