状态定义： dp[i][j][u] u == 1 时表示 当端点 i， j 进行合并时(取出 val[i] 、 val[j] 时)
或 i < k < k+1 < j， key[i] 和 key[k] 可以合并 且key[k+1] 和 key[j]合并的， 区间 [i, j]内的最大价值；
u == 0 时表示 当端点 i， j 不进行合并时(不取出 val[i] 、 val[j] 时) 的 区间 [i, j]内的最大价值；
初始化：全部初始化为 0；
边界： 当 j - i == 1 时 如果可以合并 则 dp[i][j][1] = val[i] + val[j]；
状态转移方程：如果 key[i], key[j] 可以组合， 则 如果 dp[i + 1][j - 1][1] > 0 则 dp[i][j][1] = max(dp[i][j][1], dp[i+1][j⑴][1] + val[i] + val[j]);
然后对 区间划分 k = i ~ j
dp[i][j][0] = max(dp[i][j][0], max(dp[i][k][0], dp[i][k][1]) + max(dp[k+1][j][1] , dp[k+1][j][0]));
if(dp[i][k][1] > 0 && dp[k+1][j][1] > 0) dp[i][j][1] = max(dp[i][j][1], dp[i][k][1] + dp[k+1][j][1]);
接着是对u == 0时的转移(即keyi keyj 能合并时可以选择不合并)
dp[i][j][0] = max(dp[i][j][0], max(dp[i+1][j⑴][1], dp[i+1][j⑴][0]));
如果 key[i], key[j] 不能合并， 则
if(dp[i+1][j⑴][1] > 0){
dp[i][j][0] = max(dp[i][j][0], max(dp[i+1][j⑴][1], dp[i+1][j⑴][0]));
for(k = i; k < j; k++){
dp[i][j][0] = max(dp[i][j][0], max(dp[i][k][0], dp[i][k][1]) + max(dp[k+1][j][1] , dp[k+1][j][0]));
if(dp[i][k][1] > 0 && dp[k+1][j][1] > 0) dp[i][j][1] = max(dp[i][j][1], dp[i][k][1] + dp[k+1][j][1]);
}
}
else{
dp[i][j][0] = max(dp[i][j][0], dp[i+1][j⑴][0]);
for(k = i; k < j; k++){
dp[i][j][0] = max(dp[i][j][0], max(dp[i][k][0], dp[i][k][1]) + max(dp[k+1][j][1] , dp[k+1][j][0]));
if(dp[i][k][1] > 0 && dp[k+1][j][1] > 0) dp[i][j][1] = max(dp[i][j][1], dp[i][k][1] + dp[k+1][j][1]);
}
}
复杂度 O(n^3)
Thank you!
------from ProLights