力扣刷题记录: 3040. 相同分数的最大操作数目Ⅱ
本题是第 124 场双周赛的 Q3,LC竞赛分为1706。我们可以发现这个问题的子问题结构和这个问题是一样的,于是我们天然地想到类似递归或者dp这类的方法。
方法一. 递归(超时,507/549)
代码如下:
class Solution {
public:
int maxOperations(vector& nums) {
int pb = 0, pe = nums.size()-1;
int a1 = reduction(nums,pb+1,pe-1,nums[pb]+nums[pe]);
int a2 = reduction(nums,pb+2,pe,nums[pb]+nums[pb+1]);
int a3 = reduction(nums,pb,pe-2,nums[pe]+nums[pe-1]);
int ans = max(a1,a2); ans = max(ans,a3);
return ans+1;
}
int reduction(vector& nums,int pb,int pe,int score){
if(pb>=pe){
return 0;
}
bool flag1 = (nums[pb]+nums[pb+1] == score);
bool flag2 = (nums[pe]+nums[pe-1] == score);
bool flag3 = (nums[pb]+nums[pe] == score);
if(!flag1&&!flag2&&!flag3) return 0;
int a1 = flag1*reduction(nums,pb+2,pe,score)+1;
int a2 = flag2*reduction(nums,pb,pe-2,score)+1;
int a3 = flag3*reduction(nums,pb+1,pe-1,score)+1;
int ans = max(a1,a2);
ans = max(ans,a3);
return ans;
}
};
对递归进行剪枝,上一版代码无论 flag 如何都需要进行下一层递归,这一版如果 flag 是 false 那就不需要下一层递归了。这一次仍然超时,但是完成了 520/549 的样例,代码如下:
int reduction(vector& nums,int pb,int pe,int score){
if(pb>=pe){
return 0;
}
bool flag1 = (nums[pb]+nums[pb+1] == score);
bool flag2 = (nums[pe]+nums[pe-1] == score);
bool flag3 = (nums[pb]+nums[pe] == score);
if(!flag1&&!flag2&&!flag3) return 0;
int ans = 0;
if(flag1)
{
int a1 = reduction(nums,pb+2,pe,score)+1;
ans = max(ans,a1);
}
if(flag2){
int a2 = reduction(nums,pb,pe-2,score)+1;
ans = max(ans,a2);
}
if(flag3){
int a3 = flag3*reduction(nums,pb+1,pe-1,score)+1;
ans = max(ans,a3);
}
return ans;
}
方法二. 记忆化搜索(时间超过 50.23% python3 用户)
C++版本的记忆化搜索老出bug(汗),于是汗流浃背地改成了写 python,一个 @cache 搞定,代码如下:
class Solution:
def maxOperations(self, nums: List[int]) -> int:
@cache
def reduction(pb:int, pe:int, score:int) -> int:
if pb >= pe:
return 0
flag1 = (nums[pb] + nums[pe] == score)
flag2 = (nums[pb] + nums[pb+1] == score)
flag3 = (nums[pe] + nums[pe-1] == score)
if (flag1==0) and (flag2==0) and (flag3==0):
return 0
a1=a2=a3=-100
if flag1:
a1 = reduction(pb+1,pe-1,score)+1
if flag2:
a2 = reduction(pb+2,pe,score)+1
if flag3:
a3 = reduction(pb,pe-2,score)+1
return max(a1,a2,a3)
pb=0
pe=len(nums)-1
a11 = reduction(pb+1,pe-1,nums[pb]+nums[pe])+1
a12 = reduction(pb+2,pe,nums[pb+1]+nums[pb])+1
a13 = reduction(pb,pe-2,nums[pe]+nums[pe-1])+1
return max(a11,a12,a13)
python 除了耗时不太好以外,拿来做题太方便了。