题目链接：

id=1651">点击打开链

题意：

给定一个数组，每次能够选择内部的一个数 i 消除，获得的价值就是 a[i-1] * a[i] * a[i+1]

问最小价值

思路：

dp[l,r] = min( dp[l, i] + dp[i, r] + a[l] * a[i] * a[r]);

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstring>

#include <cmath>

using namespace std;

const int N = 105;

const int inf = 100000000;

int a[N], dp[N][N], n;

int dfs(int l, int r){//返回 把区间l,r合并，最后仅仅剩下a[l]和a[r]能获得的最小价值

    if(l > r) return 0;

    if(dp[l][r] != -1)return dp[l][r];//若区间[l,r]已经计算过则不再计算

    if(l == r || l+1 == r) return dp[l][r] = 0;//仅仅有1个或者2个元素则价值是0

    int ans = inf;

    for(int i = l+1; i < r; i++)

        ans = min(ans, a[i] * a[l] * a[r] + dfs(l, i) + dfs(i, r));

    return dp[l][r] = ans;

}

int main(){

    while(cin>>n){

        for(int i = 1; i <= n; i++)scanf("%d", &a[i]);

        memset(dp, -1, sizeof dp);

        cout<<dfs(1, n)<<endl;

    }

    return 0;

}