🔗 🟡 3040. Maximum Number of Operations With the Same Score II 1709

tags: `Biweekly Contest 124` `動態規劃(DP)` `記憶化搜索(Memoization)`

題意

給定一個整數陣列 $nums$ ，如果 $nums$ 至少包含 $2$ 個元素，你可以執行以下操作中的任意一個：

選擇 $nums$ 中最前面兩個元素並且刪除它們。
選擇 $nums$ 中最後兩個元素並且刪除它們。
選擇 $nums$ 中第一個和最後一個元素並且刪除它們。

一次操作的分數是被刪除元素的和，你的任務是在確保每次操作分數相同的前提下，返回滿足上述條件的最大操作次數。

思路：記憶化搜索(Memoization)

根據題意，我們可以定義一個遞迴函數 $\rm{dfs}(\rm{target}, i, j)$ ，它表示在區間 $nums[i:j+1]$ 中，以 $target$ 為每次操作的分數時，能夠進行的最大操作次數。由於計算時會出現重複的子問題，我們可以使用記憶化搜索(Memoization) 來解決問題。

遞迴函數的具體步驟如下：

如果區間內的數字小於 $2$ 個，即 $i \geq j$ ，則返回 $0$ ，表示不能再進行操作。
在區間 $nums[i:j+1]$ $n u m s [i : j + 1]$ 中，檢查三種可能的操作：
- 使用左邊的兩個數字 $nums[i]$ 和 $nums[i+1]$ 。如果它們的和等於 $target$ ，則遞迴 $\rm{dfs}(target, i+2, j)$ 計算剩餘區間內的最大操作次數。
- 使用右邊的兩個數字 $nums[j-1]$ 和 $nums[j]$ 。如果它們的和等於 $target$ ，則遞迴 $\rm{dfs}(target, i, j-2)$ 計算剩餘區間內的最大操作次數。
- 使用左右各一個數字 $nums[i]$ 和 $nums[j]$ 。如果它們的和等於 $target$ ，則遞迴 $\rm{dfs}(target, i+1, j-1)$ 計算剩餘區間內的最大操作次數。

由於第一次操作有三種可能的 $target$ ，我們需要計算三種情況的最大值，再加上 $1$ （表示第一次操作）。

複雜度分析

時間複雜度： $\mathcal{O}(n^2)$ $O (n^{2})$ ，其中 $n$ $n$ 為陣列的長度。
- 目標分數最多只有 $3$ 種可能，在確定目標分數後，總共只有 $O(n^2)$ 種可能的區間。
空間複雜度： $\mathcal{O}(n^2)$ ，記憶化搜索的空間複雜度。

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        n = len(nums)
        @cache
        def dfs(target, i, j):  # (目標值, 左邊界, 右邊界)
            if i >= j:  # 區間內的數字小於2個
                return 0
            res = 0
            if nums[i] + nums[i + 1] == target:  # 使用左邊的兩個數字
                res = max(res, 1 + dfs(target, i + 2, j))
            if nums[j - 1] + nums[j] == target:  # 使用右邊的兩個數字
                res = max(res, 1 + dfs(target, i, j - 2))
            if nums[i] + nums[j] == target:  # 使用左右各一個數字
                res = max(res, 1 + dfs(target, i + 1, j - 1))
            return res
        res1 = dfs(nums[0] + nums[1], 2, n - 1)  # 使用左邊的兩個數字當作目標值
        res2 = dfs(nums[-2] + nums[-1], 0, n - 3)  # 使用右邊的兩個數字當作目標值
        res3 = dfs(nums[0] + nums[-1], 1, n - 2)  # 使用左右各一個數字之和當作目標值
        return 1 + max(res1, res2, res3)

class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        vector<vector<int>> memo(n, vector<int>(n));
        auto helper = [&](int i, int j, int target) -> int {
            for (auto& row : memo) fill(row.begin(), row.end(), -1); // 初始化為 -1
            function<int(int, int)> dfs = [&](int i, int j) -> int {
                if (i >= j) return 0;
                if (memo[i][j] != -1) return memo[i][j];
                int res = 0;
                if (nums[i] + nums[i + 1] == target) res = max(res, 1 + dfs(i + 2, j));
                if (nums[j - 1] + nums[j] == target) res = max(res, 1 + dfs(i, j - 2));
                if (nums[i] + nums[j] == target) res = max(res, 1 + dfs(i + 1, j - 1));
                return memo[i][j] = res;
            };
            return dfs(i, j);
        };
        ans = max(ans, helper(2, n - 1, nums[0] + nums[1]));
        ans = max(ans, helper(0, n - 3, nums[n - 2] + nums[n - 1]));
        ans = max(ans, helper(1, n - 2, nums[0] + nums[n - 1]));
        return ans + 1;
    }
};