考虑先枚举所有的物品中最后拿走的，这样就分成了2个子问题，即先拿完左边的，再拿完右边的，最后拿选出的那个。令dp(i,j)表示拿完[i,j]所有物品的最小代价。你可能会说，我们拿[i,j]这一段物品的时候，i左边和j右边的第一个物品可能会不断变化，影响i和j的最终价格。其实是不会的，还是想想一开始说的整个序列枚举最后被拿走的，然后不断分割成子问题的过程，我们都是先拿走[i,j]中的所有元素，之后才会去动i-1或者j+1。所以可以澄清一下dp状态含义：dp(i,j)表示原序列中把[i,j]中的元素全拿完，其他元素全不动的最小代价。转移就很简单了，枚举区间最后被拿走的元素即可。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
using namespace std;
int t,n,a[510],b[510],dp[510][510];
int dfs(int lb,int ub)
{
if(lb>ub) return 0;
if(dp[lb][ub]<1e9) return dp[lb][ub];
if(lb==ub) return dp[lb][ub]=a[lb]+(lb==0 ? 0:b[lb-1])+(lb==n-1 ? 0:b[lb+1]);
for(int i=lb;i<=ub;++i) dp[lb][ub]=min(dp[lb][ub],dfs(lb,i-1)+dfs(i+1,ub)+a[i]+(lb==0 ? 0:b[lb-1])+(ub==n-1 ? 0:b[ub+1]));
return dp[lb][ub];
}
int main()
{
freopen("buy.in","r",stdin);
freopen("buy.out","w",stdout);
repn(tn,1)
{
scanf("%d",&n);
rep(i,n) scanf("%d",&a[i]);
rep(i,n) scanf("%d",&b[i]);
rep(i,n) rep(j,n) dp[i][j]=1e9;
printf("%d\n",dfs(0,n-1));
}
return 0;
}