Minimum number of coins for fruits

Array Dynamic Programming Queue Heap (Priority Queue) Monotonic Queue

48.8% acceptance

Feb 25, 2026

316

You are given an 0-indexed integer array prices where prices[i] denotes the number of coins needed to purchase the (i + 1)th fruit. The fruit market has the following reward for each fruit: If you purchase the (i + 1)th fruit at prices[i] coins, you can get any number of the next i fruits for free. Note that even if you can take fruit j for free, you can still purchase it for prices[j - 1] coins to receive its reward. Return the minimum number of coins needed to acquire all the fruits.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_coins(prices: Vec<i32>) -> i32 {
    let n = prices.len();
    // dp[i] = min coins to acquire all fruits 1..=n starting from fruit i+1 (1-indexed)
    // If we buy fruit i+1 (0-indexed i), we can get fruits i+2..=2i+2 for free
    // dp[i] = prices[i] + min(dp[i+1], dp[i+2], ..., dp[min(2i+2, n)])
    // Base: dp[n] = 0
    let mut dp = vec![i32::MAX; n + 1];
    dp[n] = 0;
    for i in (0..n).rev() {
      // Buying fruit i (0-indexed) gives next i+1 fruits free (indices i+1..=2i+1)
      // So the next purchase can be at j in [i+1, min(2i+2, n)]
      let max_j = (2 * i + 2).min(n);
      for j in (i + 1)..=max_j {
        dp[i] = dp[i].min(prices[i] + dp[j]);
      }
    }
    dp[0]
  }
}