生活随笔
收集整理的這篇文章主要介紹了
LeetCode 546. 移除盒子（DP）*
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
文章目錄
1. 題目
給出一些不同顏色的盒子，盒子的顏色由數(shù)字表示，即不同的數(shù)字表示不同的顏色。
你將經(jīng)過若干輪操作去去掉盒子，直到所有的盒子都去掉為止。
每一輪你可以移除具有相同顏色的連續(xù) k 個盒子（k >= 1），這樣一輪之后你將得到 k*k 個積分。
當你將所有盒子都去掉之后，求你能獲得的最大積分和。
示例：
輸入：boxes
= [1,3,2,2,2,3,4,3,1]
輸出：
23
解釋：
[1, 3, 2, 2, 2, 3, 4, 3, 1]
----> [1, 3, 3, 4, 3, 1] (3*3=9 分
)
----> [1, 3, 3, 3, 1] (1*1=1 分
)
----> [1, 1] (3*3=9 分
)
----> [] (2*2=4 分
)提示：
1 <= boxes
.length
<= 100
1 <= boxes
[i
] <= 100
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/remove-boxes
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。
2. 解題
- 參考官方的思路
- dp[i][j][k] 表示區(qū)間[i,j]后面有 k 個連續(xù)元素跟 j 下標處相同
- 兩種辦法，1，消除右側的k+1個一樣的 dp[i][j][k] = dp[i][j-1][0] + (k+1)*(k+1)
- 2，枚舉左側的中間點 p in [i, j-1]，當b[p]==b[j]時，消除[p+1,j-1]區(qū)間，dp[i][j][k] = dp[p+1][j-1][0] + dp[i][p][k+1]
class Solution {
public:int removeBoxes(vector
<int>& boxes
) {int dp
[101][101][101];memset(dp
, 0, sizeof dp
);int n
= boxes
.size(), i
, j
, k
, p
, len
;for(len
= 1; len
<= n
; len
++) {for(i
= 0; i
+len
-1 < n
; ++i
){j
= i
+len
-1;for(k
= 0; k
< n
; ++k
){dp
[i
][j
][k
] = max(dp
[i
][j
][k
], (j
-1 < i
? 0 : dp
[i
][j
-1][0])+(k
+1)*(k
+1));for(p
= i
; p
<= j
-1; p
++){if(boxes
[p
] == boxes
[j
]){dp
[i
][j
][k
] = max(dp
[i
][j
][k
], (p
+1 > j
-1 ? 0 : dp
[p
+1][j
-1][0]) + dp
[i
][p
][k
+1]);}}}}}return dp
[0][n
-1][0];}
};class Solution {
public:int dp
[100][100][100];int removeBoxes(vector
<int>& boxes
) {memset(dp
, 0, sizeof dp
);return calculatePoints(boxes
, 0, boxes
.size() - 1, 0);}int calculatePoints(vector
<int>& boxes
, int l
, int r
, int k
) {if (l
> r
) return 0;if (dp
[l
][r
][k
] != 0) return dp
[l
][r
][k
];while (r
> l
&& boxes
[r
] == boxes
[r
- 1]) {r
--;k
++;}dp
[l
][r
][k
] = calculatePoints(boxes
, l
, r
- 1, 0) + (k
+ 1) * (k
+ 1);for (int i
= l
; i
< r
; i
++) {if (boxes
[i
] == boxes
[r
]) {dp
[l
][r
][k
] = max(dp
[l
][r
][k
], calculatePoints(boxes
, l
, i
, k
+ 1) + calculatePoints(boxes
, i
+ 1, r
- 1, 0));}}return dp
[l
][r
][k
];}
};
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
總結
以上是生活随笔為你收集整理的LeetCode 546. 移除盒子（DP）*的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
