# Find Minimum Cost to Remove Array Elements
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-minimum-cost-to-remove-array-elements)
Canonical: https://scaleengineer.com/dsa/problems/find-minimum-cost-to-remove-array-elements
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given an integer array `nums`. Your task is to remove **all elements** from the array by performing one of the following operations at each step until `nums` is empty:

* Choose any two elements from the first three elements of `nums` and remove them. The cost of this operation is the **maximum** of the two elements removed.
* If fewer than three elements remain in `nums`, remove all the remaining elements in a single operation. The cost of this operation is the **maximum** of the remaining elements.

Return the **minimum** cost required to remove all the elements.

**Example 1:**

**Input:** nums = \[6,2,8,4\]

**Output:** 12

**Explanation:**

Initially, `nums = [6, 2, 8, 4]`.

* In the first operation, remove `nums[0] = 6` and `nums[2] = 8` with a cost of `max(6, 8) = 8`. Now, `nums = [2, 4]`.
* In the second operation, remove the remaining elements with a cost of `max(2, 4) = 4`.

The cost to remove all elements is `8 + 4 = 12`. This is the minimum cost to remove all elements in `nums`. Hence, the output is 12.

**Example 2:**

**Input:** nums = \[2,1,3,3\]

**Output:** 5

**Explanation:**

Initially, `nums = [2, 1, 3, 3]`.

* In the first operation, remove `nums[0] = 2` and `nums[1] = 1` with a cost of `max(2, 1) = 2`. Now, `nums = [3, 3]`.
* In the second operation remove the remaining elements with a cost of `max(3, 3) = 3`.

The cost to remove all elements is `2 + 3 = 5`. This is the minimum cost to remove all elements in `nums`. Hence, the output is 5.

**Constraints:**

* `1 <= nums.length <= 1000`
* `1 <= nums[i] <= 106`

# Approaches
## Brute-Force Recursion
This approach directly translates the problem description into a recursive solution. We define a function that takes the current state of the array (as a list) and explores all possible moves. At each step, with at least three elements, we try all three ways to remove two of the first three elements. For each choice, we calculate the cost and make a recursive call with the updated, smaller array. The function returns the minimum cost among the three choices. The base cases for the recursion are when the array has fewer than three elements.
**Time:** O(3^(N/2) * N). At each step (where we reduce the size by 2), we branch into 3 possibilities. This leads to roughly 3^(N/2) calls. The `* N` factor comes from the potential cost of creating a new list in each recursive call. · **Space:** O(N^2), where N is the number of elements. The recursion can go up to N/2 levels deep, and at each level, we might create a new list of size up to N.
**Pros:** Simple to understand and implement as it directly follows the problem's rules.
**Cons:** Extremely inefficient due to its exponential time complexity.; Leads to a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.; Involves creating many new list objects, which is memory and time-intensive.
### Explanation
The brute-force method explores every possible sequence of removal operations. A recursive function can model this process. The state of our recursion is the current list of numbers. When the list has three or more elements, we branch out into three recursive calls, each corresponding to one of the three possible pairs we can remove from the first three elements. This creates a large tree of recursive calls. Many of the subproblems (i.e., recursive calls with the same list of remaining elements) are computed multiple times, leading to the exponential time complexity. While simple to conceptualize, this approach is not feasible for an array size up to 1000.
### Algorithm
*   Define a recursive function, say `solve(currentNums)`, that takes the current list of numbers as an argument.
*   **Base Cases:**
    *   If `currentNums` is empty, the cost is 0.
    *   If `currentNums` has 1 or 2 elements, the cost is the maximum of these elements, as per the second rule. Return this cost.
*   **Recursive Step:**
    *   If `currentNums` has 3 or more elements, consider the first three: `a`, `b`, and `c`.
    *   Explore the three possible moves:
        1.  Remove `a` and `b`. The cost is `max(a, b)` plus the result of a recursive call `solve()` on the new list `[c, d, e, ...]`.
        2.  Remove `a` and `c`. The cost is `max(a, c)` plus the result of `solve()` on the new list `[b, d, e, ...]`. 
        3.  Remove `b` and `c`. The cost is `max(b, c)` plus the result of `solve()` on the new list `[a, d, e, ...]`. 
    *   The function returns the minimum of the costs from these three options.
*   The initial call would be `solve(nums)`.

## Dynamic Programming with Two State Types
The brute-force approach is slow because it recomputes the same subproblems. We can optimize this using dynamic programming. A careful analysis of the subproblems reveals that they always take one of two forms: either removing a standard suffix of the array `nums[i:]`, or removing an array formed by a single 'out-of-order' element `nums[j]` followed by a suffix `nums[k:]`. This allows us to define two DP tables: `dp[i]` for the first case and `g[j][k]` for the second. By establishing recurrence relations for both and solving them in a bottom-up manner, we can find the solution efficiently.
**Time:** O(N^2). The main work is filling the `g` table, which has `O(N^2)` states. Each state is computed in O(1) time based on previously computed states. · **Space:** O(N^2), for the `g` table which stores results for subproblems of the form `(j, k)`.
**Pros:** Guaranteed to find the optimal solution.; Efficient enough for the given constraints (N <= 1000).
**Cons:** Requires O(N^2) space, which can be large for very big N (though acceptable for N=1000).; The logic with two interacting DP tables is more complex to understand and implement correctly.
### Explanation
This approach avoids recomputing subproblems by storing their results in memoization tables. We identify two types of subproblems that can arise.

1.  **Type 1: Suffix Subproblem.** The task is to clear a contiguous suffix of the original array, `nums[i:]`. We define `dp[i]` as the minimum cost for this.
2.  **Type 2: General Subproblem.** After an operation like removing `nums[i]` and `nums[i+2]`, the remaining array starts with `nums[i+1]` followed by `nums[i+3:]`. This is a non-contiguous subsequence of the original array. We can characterize this state by the first element's original index, `j`, and the starting index of the suffix, `k`. We define `g[j][k]` as the minimum cost for an array formed by `[nums[j]]` followed by `nums[k:]`.

We can build the `dp` and `g` tables iteratively, starting from the end of the array. We loop `i` from `n-1` down to `0`. In each step, we calculate `dp[i]` and `g[j][i]` for all `j < i`. The dependencies in the recurrence relations are always on states with larger indices, which will have already been computed. The final answer is `dp[0]`. Using `long` for costs prevents potential integer overflow during intermediate calculations.

```java
class Solution {
    public int findMinimumCost(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0], nums[1]);

        // g[j][k] stores the min cost for an array formed by nums[j] followed by nums[k:]
        long[][] g = new long[n][n + 3];
        // dp[i] stores the min cost for the suffix nums[i:]
        long[] dp = new long[n + 3];

        for (int i = n - 1; i >= 0; i--) {
            // Compute dp[i]
            if (i == n - 1) {
                dp[i] = nums[i];
            } else if (i == n - 2) {
                dp[i] = Math.max(nums[i], nums[i + 1]);
            } else {
                long cost1 = (long)Math.max(nums[i], nums[i + 1]) + dp[i + 2];
                long cost2 = (long)Math.max(nums[i], nums[i + 2]) + g[i + 1][i + 3];
                long cost3 = (long)Math.max(nums[i + 1], nums[i + 2]) + g[i][i + 3];
                dp[i] = Math.min(cost1, Math.min(cost2, cost3));
            }

            // Compute g[j][i] for all j < i
            // This represents the cost for a list starting with nums[j] followed by nums[i:]
            for (int j = i - 1; j >= 0; j--) {
                if (i == n - 1) {
                    g[j][i] = Math.max(nums[j], nums[i]);
                } else {
                    long cost1 = (long)Math.max(nums[j], nums[i]) + dp[i + 1];
                    long cost2 = (long)Math.max(nums[j], nums[i + 1]) + g[i][i + 2];
                    long cost3 = (long)Math.max(nums[i], nums[i + 1]) + g[j][i + 2];
                    g[j][i] = Math.min(cost1, Math.min(cost2, cost3));
                }
            }
        }

        return (int)dp[0];
    }
}
```
### Algorithm
*   **Observation:** Any subproblem generated during the process consists of either a contiguous suffix of the original array `nums[i:]` or a single element `nums[j]` followed by a contiguous suffix `nums[k:]` (where `j < k`).
*   **DP States:**
    *   `dp[i]`: The minimum cost to remove the suffix `nums[i:]`.
    *   `g[j][k]`: The minimum cost to remove a list formed by `nums[j]` followed by `nums[k:]`.
*   **Recurrence Relations:**
    *   For `dp[i]` (with `n-i >= 3`):
        `dp[i] = min(`
            `max(nums[i], nums[i+1]) + dp[i+2],`
            `max(nums[i], nums[i+2]) + g[i+1][i+3],`
            `max(nums[i+1], nums[i+2]) + g[i][i+3]`
        `)
    *   For `g[j][k]` (with `n-k >= 2`):
        `g[j][k] = min(`
            `max(nums[j], nums[k]) + dp[k+1],`
            `max(nums[j], nums[k+1]) + g[k][k+2],`
            `max(nums[k], nums[k+1]) + g[j][k+2]`
        `)
*   **Base Cases:**
    *   `dp[n] = 0`, `dp[n-1] = nums[n-1]`, `dp[n-2] = max(nums[n-2], nums[n-1])`.
    *   `g[j][k]` where `n-k < 2`: If `k >= n`, the list is `[nums[j]]`, cost is `nums[j]`. If `k = n-1`, list is `[nums[j], nums[n-1]]`, cost is `max(nums[j], nums[n-1])`.
*   **Implementation:** Use a bottom-up approach. Iterate `i` from `n-1` down to `0`. In each iteration, compute `dp[i]` and `g[j][i]` for all `j < i`. The required values `dp[i+x]` and `g[...][i+y]` will have been computed in previous iterations.