狀態定義： 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
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
