题目链接:https://vjudge.net/contest/308310#problem/E
题目大意:给你一串数字,头尾不能动,每次取出一个数字,这个数字贡献=该数字与左右相邻数字的乘积,求一个最小值。

思路:刚开始想的是dp[L][R]为把区间[L, R]的数字全部取完的最小代价,枚举第一次取的数字k。然后发现维护不了。因为把第一次把k取了,对子区间有影响,a[k+1]左边的数字变了。变成什么,还要看左区间怎么取,还有左右区间取数字的先后。同理:右区间也一样。所以:这个子结构并没有无后效性,因为子问题的结果具有不确定性。

因为题目中1和n不能取。
那么我们定义:dp[L][R]:区间[L, R]并且a[L]和a[R]不能取,把其他数字取完的最小代价。

根据上一篇博客:我们把k定义为区间[L, R]最后一个取的数字。

那么取走k的代价一定为a[L] * a[k] * a[R].

子问题变成:dp[L][k]和dp[k][R],因为k是最后取,所以在子问题中变成不可取。符合定义,子问题是确定的,具有无后效性。

代码有dfs深搜写法和递推写法

//dfs
#include<bits/stdc++.h>

#define LL long long
using namespace std;

int a[105];
int dp[105][105];

int dfs(int L, int R)
{
    if(dp[L][R])
    {
        return dp[L][R];
    }
    if(R-L<2)
    {
        return 0;
    }
    if(R-L==2)
    {
        return dp[L][R]=a[L]*a[L+1]*a[R];
    }
    dp[L][R]=(1<<31)-1;
    for(int k=L+1;k<=R-1;k++)
    {
        dp[L][R]=min(dp[L][R], dfs(L, k)+dfs(k, R)+a[L]*a[k]*a[R]);
    }

    return dp[L][R];
}

int main()
{
    int n;
    memset(dp, 0, sizeof(dp));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    cout<<dfs(1, n)<<endl;

    return 0;
}
//递推
#include<bits/stdc++.h>

#define LL long long
using namespace std;

int a[105];
int dp[105][105];

int dfs(int n)
{
    for(int Len=3;Len<=n;Len++)
    {
        for(int L=1;L+Len-1<=n;L++)
        {
            int R=L+Len-1;
            dp[L][R]=(1<<31)-1;
            for(int k=L+1;k<=R-1;k++)
            {
                dp[L][R]=min(dp[L][R], dp[L][k]+dp[k][R]+a[L]*a[k]*a[R]);
            }
        }
    }

    return dp[1][n];
}

int main()
{
    int n;
    memset(dp, 0, sizeof(dp));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    cout<<dfs(n)<<endl;

    return 0;
}