本文共 2187 字，大约阅读时间需要 7 分钟。

这个题令我对区间dp有了新的理解，很满足能够在做题慢的情况下能够对题目所涉及的知识最大程度掌握

memset(dp,INF,sizeof(dp));        for(int i=1;i<=n;i++)            dp[i][i]=a[i]+b[i-1]+b[i+1];///区间长度为1的时候的情况        for(int len=2;len<=n;len++)///枚举所有可能的区间长度        {               for(int i=1;i<=n-len+1;i++)///枚举所有可能的起点            {                   int j=i+len-1;///j代表区间的右端点///即区间[i,j]                dp[i][j]=min(dp[i+1][j]+a[i]+b[i-1]+b[j+1],dp[i][j-1]+a[j]+b[i-1]+b[j+1]);///先考虑左右端点时候的特殊情况                for(int k=i+1;k

但我后来反思了，其实这里可以简化（先看图片解释的思路，再看代码）：

memset(dp, 0, sizeof(dp));	for (int i = 1; i <= n; i++)		dp[i][i] = a[i] + b[i - 1] + b[i + 1];//2.初始化用到了区间化思想（区间dp）	for (int len = 1; len < n; len++)	{   		for (int i = 1; i + len <= n; i++)		{   			int j = i + len;			//dp[i][j] = min(dp[i + 1][j] + a[i] + b[i - 1] + b[j + 1], dp[i][j - 1] + a[j] + b[i - 1] + b[j + 1]);//3.边界条件的处理			dp[i][j] = inf;			for (int k = i; k <= j; k++)			{   				dp[i][j] = min(dp[i][k - 1] + dp[k + 1][j] + a[k] + b[i - 1] + b[j + 1], dp[i][j]);			}		}	}

全代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int N = 300;const int inf = 0x3f3f3f3f;int n;int  a[N];int  b[N];int solve();int dp[N][N];int main(){   	int t = 1;	int T;	cin >> T;	while (T--)	{   		cin >> n;		for (int i = 1; i <= n; i++)			cin >> a[i];		for (int i = 1; i <= n; i++)			cin >> b[i];		cout << "Case #" << t++ << ": " << solve() << endl;	}}int solve(){   	a[0] = b[0] = a[n + 1] = b[n + 1] = 0;//1.边界条件的初始化	memset(dp, 0, sizeof(dp));	for (int i = 1; i <= n; i++)		dp[i][i] = a[i] + b[i - 1] + b[i + 1];//2.初始化用到了区间化思想（区间dp）	for (int len = 1; len < n; len++)	{   		for (int i = 1; i + len <= n; i++)		{   			int j = i + len;			//dp[i][j] = min(dp[i + 1][j] + a[i] + b[i - 1] + b[j + 1], dp[i][j - 1] + a[j] + b[i - 1] + b[j + 1]);//3.边界条件的处理			dp[i][j] = inf;			for (int k = i; k <= j; k++)			{   				dp[i][j] = min(dp[i][k - 1] + dp[k + 1][j] + a[k] + b[i - 1] + b[j + 1], dp[i][j]);			}		}	}	return dp[1][n];}
      
     
    
   

这个题目使我对区间dp第二种表达方式有了一定的理解，在这里归纳一下

转载地址：http://vvrq.baihongyu.com/