Minimum array sum

Array Dynamic Programming

31.0% acceptance

Feb 24, 2026

171

You are given an integer array nums and three integers k, op1, and op2. You can perform the following operations on nums: Operation 1: Choose an index i and divide nums[i] by 2, rounding up to the nearest whole number. You can perform this operation at most op1 times, and not more than once per index. Operation 2: Choose an index i and subtract k from nums[i], but only if nums[i] is greater than or equal to k. You can perform this operation at most op2 times, and not more than once per index. Note: Both operations can be applied to the same index, but at most once each. Return the minimum possible sum of all elements in nums after performing any number of operations.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_array_sum(nums: Vec<i32>, k: i32, op1: i32, op2: i32) -> i32 {
    // DP: dp[i][o1][o2] = min sum considering first i elements with o1 op1s and o2 op2s remaining
    let _n = nums.len();
    let op1 = op1 as usize;
    let op2 = op2 as usize;
    // dp[o1][o2] = min sum so far
    let mut dp = vec![vec![0i32; op2 + 1]; op1 + 1];
    // All start at 0 (no elements processed yet)
    
    for &v in &nums {
      let mut ndp = vec![vec![i32::MAX; op2 + 1]; op1 + 1];
      for a in 0..=op1 {
        for b in 0..=op2 {
          if dp[a][b] == i32::MAX { continue; }
          let base = dp[a][b];
          // Option 1: no ops on this element
          ndp[a][b] = ndp[a][b].min(base + v);
          // Option 2: only op1
          if a > 0 {
            let v1 = (v + 1) / 2;
            ndp[a-1][b] = ndp[a-1][b].min(base + v1);
          }
          // Option 3: only op2
          if b > 0 && v >= k {
            let v2 = v - k;
            ndp[a][b-1] = ndp[a][b-1].min(base + v2);
          }
          // Option 4: both op1 and op2 (order matters: op2 then op1 vs op1 then op2)
          if a > 0 && b > 0 {
            // op1 then op2: ceil(v/2) - k if >= k
            let v1 = (v + 1) / 2;
            if v1 >= k {
              ndp[a-1][b-1] = ndp[a-1][b-1].min(base + v1 - k);
            } else {
              // can't apply op2 after op1
              ndp[a-1][b-1] = ndp[a-1][b-1].min(base + v1);
            }
            // op2 then op1: ceil((v-k)/2)
            if v >= k {
              let v2 = v - k;
              let v21 = (v2 + 1) / 2;
              ndp[a-1][b-1] = ndp[a-1][b-1].min(base + v21);
            }
          }
        }
      }
      dp = ndp;
    }
    
    dp.iter().flat_map(|row| row.iter()).cloned().filter(|&x| x != i32::MAX).min().unwrap_or(0)
  }
}