区间dp

Bertha 。 2023-07-10 08:18 38阅读 0赞

**概念**  
区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。  
借鉴大佬总结：[猛戳][Link 1]

**过程**  
区间dp的过程其实就是三步（就是三个for循环）  
*区间长度==>起始点==>分割点*  
从求小区间的最优解，再合并小区间到大区间。

**状态转移方程**  
dp\[i\]\[j\]表示从i到j区间的最优解，所以一般情况下要得到的结果就是dp\[1\]\[n\] (感觉我个人最费解的就是这个部分，所以就直接点描述dp数组)。按照区间长度，起始点以及分割点的思路可以得到状态转移方程

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+价值数组)

## 题目 ##

**石子归并**  
N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。  
例如： 1 2 3 4，有不少合并方法  
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)  
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)  
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)  
括号里面为总代价可以看出，第一种方法的代价最低，现在给出n堆石子的数量，计算最小合并代价。  
**输入**  
第1行：N（2 <= N <= 100) 第2 - N + 1：N堆石子的数量（1 <= Ai <= 10000)  
**输出**  
输出最小合并代价

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    #define inf 0x3f3f3f
    int dp[1010][1010];
    int main()
    { 
    	int n;
    	while(cin>>n)
    	{ 
    		int x;
    		int a[1010];
    		memset(dp,inf,sizeof(dp));//dp初始化为一个很大的值 
    		a[0]=0;
    		for(int i=1;i<=n;i++)
    		{ 
    			scanf("%d",&x);
    			a[i]=a[i-1]+x;
    			dp[i][i]=0;//i到i区间值为0 
    		}
    		int i,j,k,endl;
    		for(int i=1;i<=n;i++)//枚举长度 
    		{ 
    			for(j=1;j<=n-i+1;j++)//枚举起点 
    			{ 
    				endl=j+i-1;
    				for(k=j;k<endl;k++)
    				dp[j][endl]=min(dp[j][endl],dp[j][k]+dp[k+1][endl]+a[endl]-a[j-1]);//这里的a[endl]-a[j-1]要注意，因为是求j~endl的和 ,我一开始就写的a[j] ,然后裂开了 
    			} 
    		}
    		printf("%d\n",dp[1][n]); 
    	}
    }

\*\*Cutting Sticks \*\*  
（题目全是英语的就不做搬运工了）  
题意：一个len（木块长度），一个n（木块上可以切割的地方），然后n个数字，表示切割点。每次切割的代价是待切割木块的总长度。  
问：最小代价  
做完石子合并后做这个差点裂开了，学完区间dp，按照daolao的指导先ac了石子合并，但这个题目感觉和石子合并就反着来，特别是求价值数组的时候。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    #define inf 0x3f3f3f
    int dp[1010][1010];
    int main()
    { 
    	int n,len;
    	while(cin>>len>>n&&len)
    	{ 
    		int x;
    		int a[1010];
    		//memset(dp,inf,sizeof(dp));//dp初始化为一个很大的值 
    		a[0]=0;
    		for(int i=1;i<=n;i++)
    		{ 
    			scanf("%d",&a[i]);
    			dp[i][i]=0;//i到i区间值为0 
    		}
    		n+=1;
    		a[n]=len;
    		int i,j,k,endl;
    		for(int i=2;i<=n;i++)//枚举长度 
    		{ 
    			for(j=0;j<=n-i;j++)//枚举起点 
    			{ 
    				endl=j+i;
    				dp[j][endl]=0x3f3f3f3f;
    				for(k=j;k<=endl;k++)
    				dp[j][endl]=min(dp[j][endl],dp[j][k]+dp[k][endl]+a[endl]-a[j]); 
    			} 
    		}
    		printf("The minimum cutting is %d.\n",dp[0][n]); 
    	}
    }

[Link 1]: https://blog.csdn.net/qq_40772692/article/details/80183248?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task