【Java每日一题】2.和数最大操作II-动态规划

题目难度：中等

主要提升：for循环思想、动态规划思想、数组操作

一、题目描述：

给你一个整数数组 nums ，如果 nums 至少包含 2 个元素，你可以执行以下操作中的任意一个：
（1）选择 nums 中最前面两个元素并且删除它们。
（2）选择 nums 中最后两个元素并且删除它们。
（3）选择 nums 中第一个和最后一个元素并且删除它们。
一次操作的分数是被删除元素的和。
在确保 所有操作分数相同 的前提下，请你求出最多能进行多少次操作。
请你返回按照上述要求 最多可以进行的操作次数。

二、示例：

示例 1：
输入：nums = [3,2,1,2,3,4]
输出：3
解释：我们执行以下操作：
– 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。
– 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。
– 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。
由于 nums 为空，我们无法继续进行任何操作。
示例 2：
输入：nums = [3,2,6,1,4]
输出：2
解释：我们执行以下操作：
– 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。
– 删除最后两个元素，分数为 1 + 4 = 5 ，nums = [6] 。
至多进行 2 次操作。

三、思路：

要使用动态规划的思想，对于三种情况分别进行计算，返回最优解为最大次数。

四、代码：

参考Leetcode：

class Solution {
    int[] nums;
    int[][] memo;

    public int maxOperations(int[] nums) {
        // 初始化变量
        int n = nums.length; // 获取输入数组的长度
        this.nums = nums; // 将输入数组赋值给类的成员变量
        this.memo = new int[n][n]; // 创建一个二维数组用于记忆化搜索
        int res = 0; // 初始化结果变量为0

        // 尝试三种不同的操作并取最大值
        res = Math.max(res, helper(0, n - 1, nums[0] + nums[n - 1]));
        res = Math.max(res, helper(0, n - 1, nums[0] + nums[1]));
        res = Math.max(res, helper(0, n - 1, nums[n - 2] + nums[n - 1]));

        return res; // 返回最终结果
    }

    public int helper(int i, int j, int target) {
        // 重置记忆化数组
        for (int k = 0; k = j) {
            return 0;
        }
        // 如果已经计算过这个子问题，直接返回记忆化的结果
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        // 初始化答案为0
        int ans = 0;
        // 检查三种可能的操作
        if (nums[i] + nums[i + 1] == target) {
            ans = Math.max(ans, dfs(i + 2, j, target) + 1);
        }
        if (nums[j - 1] + nums[j] == target) {
            ans = Math.max(ans, dfs(i, j - 2, target) + 1);
        }
        if (nums[i] + nums[j] == target) {
            ans = Math.max(ans, dfs(i + 1, j - 1, target) + 1);
        }
        // 记忆化当前的结果
        memo[i][j] = ans;
        // 返回答案
        return ans;
    }
}