2944. Minimum Number of Coins for Fruits

Approach 1: Straightforward

• Time: $O(n^2)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  int minimumCoins(vector<int>& prices) {
    const int n = prices.size();
    vector<int> dp(n + 1, INT_MAX);
    dp[n] = 0;

    for (int i = n - 1; i >= 0; --i)
      for (int j = i + 1; j <= min((i + 1) * 2, n); ++j)
        dp[i] = min(dp[i], prices[i] + dp[j]);

    return dp[0];
  }
};

class Solution {
  public int minimumCoins(int[] prices) {
    final int n = prices.length;
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[n] = 0;

    for (int i = n - 1; i >= 0; --i)
      for (int j = i + 1; j <= Math.min((i + 1) * 2, n); ++j)
        dp[i] = Math.min(dp[i], prices[i] + dp[j]);

    return dp[0];
  }
}

class Solution:
  def minimumCoins(self, prices: list[int]) -> int:
    n = len(prices)
    # Convert to 0-indexed for easy computation.
    # dp[i] := the minimum number of coins to acquire fruits[i:]
    dp = [math.inf] * n + [0]

    for i in range(n - 1, -1, -1):
      # Convert back to 1-indexed.
      for j in range(i + 1, min((i + 1) * 2 + 1, n + 1)):
        dp[i] = min(dp[i], prices[i] + dp[j])

    return dp[0]

Approach 2: Priority Queue

• Time: $O(n\log n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  int minimumCoins(vector<int>& prices) {
    const int n = prices.size();
    int ans = 0;
    using P = pair<int, int>;
    // Stores (dp[i], i), where dp[i] := the minimum number of coins to acquire
    // fruits[i:] (0-indexed).
    priority_queue<P, vector<P>, greater<>> minHeap;
    minHeap.emplace(0, n);

    for (int i = n - 1; i >= 0; --i) {
      while (!minHeap.empty() && minHeap.top().second > (i + 1) * 2)
        minHeap.pop();
      ans = prices[i] + minHeap.top().first;
      minHeap.emplace(ans, i);
    }

    return ans;
  }
};

class Solution {
  public int minimumCoins(int[] prices) {
    final int n = prices.length;
    int ans = 0;
    // Stores (dp[i], i), where dp[i] := the minimum number of coins to acquire
    // fruits[i:] (0-indexed).
    Queue<Pair<Integer, Integer>> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey));
    minHeap.offer(new Pair<>(0, n));

    for (int i = n - 1; i >= 0; --i) {
      while (!minHeap.isEmpty() && minHeap.peek().getValue() > (i + 1) * 2)
        minHeap.poll();
      ans = prices[i] + minHeap.peek().getKey();
      minHeap.offer(new Pair<>(ans, i));
    }

    return ans;
  }
}

class Solution:
  def minimumCoins(self, prices: list[int]) -> int:
    n = len(prices)
    # Stores (dp[i], i), where dp[i] is the minimum number of coins to acquire
    # fruits[i:] (0-indexed).
    minHeap = [(0, n)]
    ans = 0

    for i in range(n - 1, -1, -1):
      while minHeap and minHeap[0][1] > (i + 1) * 2:
        heapq.heappop(minHeap)
      ans = prices[i] + minHeap[0][0]
      heapq.heappush(minHeap, (ans, i))

    return ans

Approach 3: Monotonic Queue

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  int minimumCoins(vector<int>& prices) {
    const int n = prices.size();
    int ans = INT_MAX;
    // Stores (dp[i], i), where dp[i] := the minimum number of coins to acquire
    // fruits[i:] (0-indexed) in ascending order.
    deque<pair<int, int>> minQ{{0, n}};

    for (int i = n - 1; i >= 0; --i) {
      while (!minQ.empty() && minQ.front().second > (i + 1) * 2)
        minQ.pop_front();
      ans = prices[i] + minQ.front().first;
      while (!minQ.empty() && minQ.back().first >= ans)
        minQ.pop_back();
      minQ.emplace_back(ans, i);
    }

    return ans;
  }
};

class Solution {
  public int minimumCoins(int[] prices) {
    final int n = prices.length;
    int ans = Integer.MAX_VALUE;
    // Stores (dp[i], i), where dp[i] := the minimum number of coins to acquire
    // fruits[i:] (0-indexed) in ascending order.
    Deque<Pair<Integer, Integer>> minQ = new ArrayDeque<>();
    minQ.offerFirst(new Pair<>(0, n));

    for (int i = n - 1; i >= 0; --i) {
      while (!minQ.isEmpty() && minQ.peekFirst().getValue() > (i + 1) * 2)
        minQ.pollFirst();
      ans = prices[i] + minQ.peekFirst().getKey();
      while (!minQ.isEmpty() && minQ.peekLast().getKey() >= ans)
        minQ.pollLast();
      minQ.offerLast(new Pair<>(ans, i));
    }

    return ans;
  }
}

class Solution:
  def minimumCoins(self, prices: list[int]) -> int:
    n = len(prices)
    ans = math.inf
    # Stores (dp[i], i), where dp[i] := the minimum number of coins to acquire
    # fruits[i:] (0-indexed) in ascending order.
    minQ = collections.deque([(0, n)])

    for i in range(n - 1, -1, -1):
      while minQ and minQ[0][1] > (i + 1) * 2:
        minQ.popleft()
      ans = prices[i] + minQ[0][0]
      while minQ and minQ[-1][0] >= ans:
        minQ.pop()
      minQ.append((ans, i))

    return ans