美团2021-10-4最优二叉树Ⅱ

小团有一个由N个节点组成的二叉树，每个节点有一个权值。定义二叉树每条边的开销为其两端节点权值的乘积，二叉树的总开销即每条边的开销之和。小团按照二叉树的中序遍历依次记录下每个节点的权值，即他记录下了N个数，第i个数表示位于中序遍历第i个位置的节点的权值。
之后由于某种原因，小团遗忘了二叉树的具体结构。在所有可能的二叉树中，总开销最小的二叉树被称为最优二叉树。现在，小团请小美求出最优二叉树的总开销。

/*
思路：
记忆化搜索
枚举每个a[i]为当前的根节点，搜索a[i]左边为左子节点，a[i]右边为右子节点，计算最大值
*/


//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>//memset头文件
using namespace std;

const int inf = 1 << 30;
const int maxn = 310;
int vis[maxn][maxn][maxn];//备忘录
vector<int> v(maxn, 0);

int dfs(int left, int right, int root)
{
	if (left > right)//不包括等号
		return 0;
	if (vis[left][right][root] != -1)//如果备忘录已经有数了，直接返回
		return vis[left][right][root];
	int res = inf;//在root结点为父节点时，i结点为根节点的最小开销

	//以当前数组第一位为根，逐个遍历可能的情况
	for (int i = left; i <= right; ++i)
	{
		int l = dfs(left, i - 1, i);//以i为根的左子树的最小开销
		int r = dfs(i + 1, right, i);//以i为根的右子树的最小开销
		res = min(res, l + r + v[i] * v[root]);
	}
	vis[left][right][root] = res;//存在备忘录
	return res;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)///从1开始存储
	{
		scanf("%d", &v[i]);
	}
	memset(vis, -1, sizeof vis);//将备忘录全置为-1
	printf("%d", dfs(1, n, 0));//假的根节点
	return 0;
}