Find minimum cost to remove array elements

Array Dynamic Programming

21.4% acceptance

Feb 25, 2026

148

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(nums: Vec<i32>) -> i64 {
    let n = nums.len();
    if n == 1 { return nums[0] as i64; }
    if n == 2 { return nums[0].max(nums[1]) as i64; }

    // dp[k]    = min cost to clear nums[k..n] with no carried-over element
    // g[k][j]  = min cost to clear {nums[j]} + nums[k..n], where j < k
    //            (nums[j] is a "leftover" element carried from a previous step)
    //
    // Recurrences (for k <= n-2, j < k):
    //   a) pair leftover nums[j] with nums[k]:   max(nums[j],nums[k])  + dp[k+1]
    //   b) pair leftover nums[j] with nums[k+1]: max(nums[j],nums[k+1])+ g[k+2][k]
    //   c) pair nums[k] with nums[k+1]:          max(nums[k],nums[k+1])+ g[k+2][j]
    //   g[k][j] = min(a, b, c)
    //
    // For dp[k] (k <= n-3):
    //   o1) pair nums[k] with nums[k+1]: max(nums[k],nums[k+1])  + dp[k+2]
    //   o2) pair nums[k] with nums[k+2]: max(nums[k],nums[k+2])  + g[k+3][k+1]
    //   o3) pair nums[k+1] with nums[k+2]: max(nums[k+1],nums[k+2])+ g[k+3][k]
    //   dp[k] = min(o1, o2, o3)

    let mut dp = vec![0i64; n + 2];
    dp[n - 1] = nums[n - 1] as i64;
    dp[n - 2] = nums[n - 2].max(nums[n - 1]) as i64;

    // g[k] only needs indices j < k, so size n suffices per row.
    let mut g = vec![vec![0i64; n]; n + 2];

    // Base: k == n  →  only the leftover remains
    for j in 0..n {
      g[n][j] = nums[j] as i64;
    }
    // Base: k == n-1  →  leftover + one element = 2 elements, remove as a pair
    for j in 0..n - 1 {
      g[n - 1][j] = nums[j].max(nums[n - 1]) as i64;
    }

    // Fill from k = n-2 down to 0
    for k in (0..n - 1).rev() {
      // Compute g[k][j] for every valid leftover index j < k
      for j in 0..k {
        let a = nums[j].max(nums[k]) as i64 + dp[k + 1];
        let b = nums[j].max(nums[k + 1]) as i64 + g[k + 2][k];
        let c = nums[k].max(nums[k + 1]) as i64 + g[k + 2][j];
        g[k][j] = a.min(b).min(c);
      }
      // Compute dp[k] when at least 3 elements remain
      if k + 2 < n {
        let o1 = nums[k].max(nums[k + 1]) as i64 + dp[k + 2];
        let o2 = nums[k].max(nums[k + 2]) as i64 + g[k + 3][k + 1];
        let o3 = nums[k + 1].max(nums[k + 2]) as i64 + g[k + 3][k];
        dp[k] = o1.min(o2).min(o3);
      }
    }

    dp[0]
  }
}