Skip to content

3366. Minimum Array Sum 👍

Approach 1: Top-down

  • Time: $O(k \cdot \texttt{op1} \cdot \texttt{op2})$
  • Space: $O(k \cdot \texttt{op1} \cdot \texttt{op2})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  int minArraySum(vector<int>& nums, int k, int op1, int op2) {
    vector<vector<vector<int>>> mem(
        nums.size(),
        vector<vector<int>>(op1 + 1, vector<int>(op2 + 1, INT_MAX)));
    return minArraySum(nums, 0, op1, op2, k, mem);
  }

 private:
  // Returns the minimum sum of nums[i..n - 1] with `op1` operations of op1 and
  // `op2` operations of op2.
  int minArraySum(const vector<int>& nums, int i, int op1, int op2, int k,
                  vector<vector<vector<int>>>& mem) {
    if (i == nums.size())
      return 0;
    if (mem[i][op1][op2] != INT_MAX)
      return mem[i][op1][op2];
    int res = nums[i] + minArraySum(nums, i + 1, op1, op2, k, mem);
    if (op1 > 0)
      res = min(res, (nums[i] + 1) / 2 +
                         minArraySum(nums, i + 1, op1 - 1, op2, k, mem));
    if (op2 > 0 && nums[i] >= k)
      res = min(res,
                nums[i] - k + minArraySum(nums, i + 1, op1, op2 - 1, k, mem));
    if (op1 > 0 && op2 > 0) {
      if ((nums[i] + 1) / 2 >= k)
        res = min(res, (nums[i] + 1) / 2 - k +
                           minArraySum(nums, i + 1, op1 - 1, op2 - 1, k, mem));
      if (nums[i] >= k)
        res = min(res, (nums[i] - k + 1) / 2 +
                           minArraySum(nums, i + 1, op1 - 1, op2 - 1, k, mem));
    }
    return mem[i][op1][op2] = res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public int minArraySum(int[] nums, int k, int op1, int op2) {
    Integer[][][] mem = new Integer[nums.length][op1 + 1][op2 + 1];
    return minArraySum(nums, 0, op1, op2, k, mem);
  }

  // Returns the minimum sum of nums[i..n - 1] with `op1` operations of op1 and
  // `op2` operations of op2.
  private int minArraySum(int[] nums, int i, int op1, int op2, int k, Integer[][][] mem) {
    if (i == nums.length)
      return 0;
    if (mem[i][op1][op2] != null)
      return mem[i][op1][op2];
    int res = nums[i] + minArraySum(nums, i + 1, op1, op2, k, mem);
    if (op1 > 0)
      res = Math.min(res, (nums[i] + 1) / 2 + minArraySum(nums, i + 1, op1 - 1, op2, k, mem));
    if (op2 > 0 && nums[i] >= k)
      res = Math.min(res, nums[i] - k + minArraySum(nums, i + 1, op1, op2 - 1, k, mem));
    if (op1 > 0 && op2 > 0) {
      if ((nums[i] + 1) / 2 >= k)
        res = Math.min(res,
                       (nums[i] + 1) / 2 - k + minArraySum(nums, i + 1, op1 - 1, op2 - 1, k, mem));
      if (nums[i] >= k)
        res = Math.min(res,
                       (nums[i] - k + 1) / 2 + minArraySum(nums, i + 1, op1 - 1, op2 - 1, k, mem));
    }
    return mem[i][op1][op2] = res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def minArraySum(self, nums: list[int], k: int, op1: int, op2: int) -> int:
    @functools.lru_cache(None)
    def dp(i: int, op1: int, op2: int) -> int:
      """
      Returns the minimum sum of nums[i..n - 1] with `op1` operations of op1 and
      `op2` operations of op2.
      """
      if i == len(nums):
        return 0
      res = nums[i] + dp(i + 1, op1, op2)
      if op1 > 0:
        res = min(res, (nums[i] + 1) // 2 + dp(i + 1, op1 - 1, op2))
      if op2 > 0 and nums[i] >= k:
        res = min(res, nums[i] - k + dp(i + 1, op1, op2 - 1))
      if op1 > 0 and op2 > 0:
        if (nums[i] + 1) // 2 >= k:
          res = min(res, (nums[i] + 1) // 2 - k + dp(i + 1, op1 - 1, op2 - 1))
        if nums[i] >= k:
          res = min(res, (nums[i] - k + 1) // 2 + dp(i + 1, op1 - 1, op2 - 1))
      return res

    return dp(0, op1, op2)

Approach 2: Bottom-up

  • Time: $O(k \cdot \texttt{op1} \cdot \texttt{op2})$
  • Space: $O(k \cdot \texttt{op1} \cdot \texttt{op2})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  int minArraySum(vector<int>& nums, int k, int op1, int op2) {
    const int n = nums.size();
    // dp[i][j][k] := the minimum sum of nums[i..n - 1] with j operations of op1
    // and k operations of op2
    vector<vector<vector<int>>> dp(
        n + 1, vector<vector<int>>(op1 + 1, vector<int>(op2 + 1, INT_MAX)));

    // Base case: When index reaches the end of the array, the result is 0.
    for (int i = 0; i <= op1; ++i)
      for (int j = 0; j <= op2; ++j)
        dp[n][i][j] = 0;

    for (int i = n - 1; i >= 0; --i)
      for (int o1 = 0; o1 <= op1; ++o1)
        for (int o2 = 0; o2 <= op2; ++o2) {
          int sum = nums[i] + dp[i + 1][o1][o2];
          if (o1 > 0)
            sum = min(sum, (nums[i] + 1) / 2 + dp[i + 1][o1 - 1][o2]);
          if (o2 > 0 && nums[i] >= k)
            sum = min(sum, nums[i] - k + dp[i + 1][o1][o2 - 1]);
          if (o1 > 0 && o2 > 0) {
            if ((nums[i] + 1) / 2 >= k)
              sum = min(sum, (nums[i] + 1) / 2 - k + dp[i + 1][o1 - 1][o2 - 1]);
            if (nums[i] >= k)
              sum = min(sum, (nums[i] - k + 1) / 2 + dp[i + 1][o1 - 1][o2 - 1]);
          }
          dp[i][o1][o2] = sum;
        }

    return dp[0][op1][op2];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
  public int minArraySum(int[] nums, int k, int op1, int op2) {
    final int n = nums.length;
    // dp[i][j][k] := the minimum sum of nums[i..n - 1] with j operations of op1
    // and k operations of op2
    int[][][] dp = new int[n + 1][op1 + 1][op2 + 1];

    Arrays.stream(dp).forEach(
        A -> Arrays.stream(A).forEach(B -> Arrays.fill(B, Integer.MAX_VALUE)));

    // Base case: When index reaches the end of the array, the result is 0.
    for (int i = 0; i <= op1; ++i)
      for (int j = 0; j <= op2; ++j)
        dp[n][i][j] = 0;

    for (int i = n - 1; i >= 0; --i)
      for (int o1 = 0; o1 <= op1; ++o1)
        for (int o2 = 0; o2 <= op2; ++o2) {
          int sum = nums[i] + dp[i + 1][o1][o2];
          if (o1 > 0)
            sum = Math.min(sum, (nums[i] + 1) / 2 + dp[i + 1][o1 - 1][o2]);
          if (o2 > 0 && nums[i] >= k)
            sum = Math.min(sum, nums[i] - k + dp[i + 1][o1][o2 - 1]);
          if (o1 > 0 && o2 > 0) {
            if ((nums[i] + 1) / 2 >= k)
              sum = Math.min(sum, (nums[i] + 1) / 2 - k + dp[i + 1][o1 - 1][o2 - 1]);
            if (nums[i] >= k)
              sum = Math.min(sum, (nums[i] - k + 1) / 2 + dp[i + 1][o1 - 1][o2 - 1]);
          }
          dp[i][o1][o2] = sum;
        }

    return dp[0][op1][op2];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
  def minArraySum(self, nums: list[int], k: int, op1: int, op2: int) -> int:
    n = len(nums)
    # dp[i][j][k] := the minimum sum of nums[i..n - 1] with j operations of op1
    # and k operations of op2
    dp = [[[math.inf] * (op2 + 1)
          for _ in range(op1 + 1)]
          for _ in range(n + 1)]

    # Base case: When index reaches the end of the array, the result is 0.
    for i in range(op1 + 1):
      for j in range(op2 + 1):
        dp[n][i][j] = 0

    for i in range(n - 1, -1, -1):
      for o1 in range(op1 + 1):
        for o2 in range(op2 + 1):
          summ = nums[i] + dp[i + 1][o1][o2]
          if o1 > 0:
            summ = min(summ, (nums[i] + 1) // 2 + dp[i + 1][o1 - 1][o2])
          if o2 > 0 and nums[i] >= k:
            summ = min(summ, nums[i] - k + dp[i + 1][o1][o2 - 1])
          if o1 > 0 and o2 > 0:
            if (nums[i] + 1) // 2 >= k:
              summ = min(summ,
                         (nums[i] + 1) // 2 - k + dp[i + 1][o1 - 1][o2 - 1])
            if nums[i] >= k:
              summ = min(summ,
                         (nums[i] - k + 1) // 2 + dp[i + 1][o1 - 1][o2 - 1])
          dp[i][o1][o2] = summ

    return dp[0][op1][op2]