(NICE!!!)LeetCode 3040. 相同分数的最大操作数目 II（深度优先搜索dfs+状态记忆化）

3040. 相同分数的最大操作数目 II

思路：记忆化搜索。一共最多三种target，我们三次记忆化搜索即可。细节看注释

class Solution {
public:
    int n;
    vector<vector<int>> v;
    //对区间l~r进行操作，返回符合target的最大操作次数
    int dfs(int l,int r,int target,vector<int>& nums){
        if(l>=r) return 0;
        if(v[l][r]!=-1) return v[l][r];
        int mx=0;
        if(nums[l]+nums[r]==target) mx=max(mx,dfs(l+1,r-1,target,nums)+1);
        if(nums[l]+nums[l+1]==target) mx=max(mx,dfs(l+2,r,target,nums)+1);
        if(nums[r]+nums[r-1]==target) mx=max(mx,dfs(l,r-2,target,nums)+1);
        return v[l][r]=mx;
    }
    int maxOperations(vector<int>& nums) {
        n=nums.size();
        v=vector<vector<int>>(n,vector<int>(n,-1));
        int mx=0;
        mx=max(mx,dfs(2,n-1,nums[0]+nums[1],nums)+1);
        v=vector<vector<int>>(n,vector<int>(n,-1));
        mx=max(mx,dfs(0,n-3,nums[n-1]+nums[n-2],nums)+1);
        v=vector<vector<int>>(n,vector<int>(n,-1));
        mx=max(mx,dfs(1,n-2,nums[0]+nums[n-1],nums)+1);
        return mx;
    }
};