首页 > 代码库 > 第十周 Leetcode 546. Remove Boxes (HARD) 记忆化搜索
第十周 Leetcode 546. Remove Boxes (HARD) 记忆化搜索
Leetcode546
给定一个整数序列，每次删除其中连续相等的子序列，得分为序列长度的平方 求最高得分。
dp方程如下：
memo[l][r][k] = max(memo[l][r][k], dfs(boxes,memo,l,i,k+1) + dfs(boxes,memo,i+1,r-1,0));
意思是在序列的l-r部分后接k长度的 r值序列 所能得到的最大得分。
代码很简单
class Solution {
public:
int removeBoxes(vector<int>& boxes) {
int n=boxes.size();
int memo[100][100][100] = {0};
return dfs(boxes,memo,0,n-1,0);
}
int dfs(vector<int>& boxes,int memo[100][100][100], int l,int r,int k){
if (l>r) return 0;
if (memo[l][r][k]!=0) return memo[l][r][k];
while (r>l && boxes[r]==boxes[r-1]) {r--;k++;}
memo[l][r][k] = dfs(boxes,memo,l,r-1,0) + (k+1)*(k+1);
for (int i=l; i<r; i++){
if (boxes[i]==boxes[r]){
memo[l][r][k] = max(memo[l][r][k], dfs(boxes,memo,l,i,k+1) + dfs(boxes,memo,i+1,r-1,0));
}
}
return memo[l][r][k];
}
};
第十周 Leetcode 546. Remove Boxes (HARD) 记忆化搜索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。