题目
题解：区间DP dp[i][j] 表示i-j的所有灯泡都熄灭了之后，能获得最大价值
代码语言：javascript复制class Solution {
public:
int dp[505][505];
int maxCoins(vector<int>& nums) {
vector<int>a;
a.push_back(1);
for(int i=0;i<nums.size();i )
{
a.push_back(nums[i]);
}
a.push_back(1);
memset(dp,0,sizeof(dp));
for(int l=0;l<nums.size();l )
{
for(int i=1;i l<=nums.size();i )
{
int j=i l;
for(int k=i;k<=j;k )
{
dp[i][j]=max(dp[i][j],dp[i][k-1] dp[k 1][j] a[k]*a[i-1]*a[j 1]);
}
}
}
return dp[1][nums.size()];
}
};
