Question

2944. Minimum Number of Coins for Fruits

中文文档

Description

You are at a fruit market with different types of exotic fruits on display.

You are given a 1-indexed array prices, where prices[i] denotes the number of coins needed to purchase the ith fruit.

The fruit market has the following offer:

• If you purchase the ith fruit at prices[i] coins, you can get 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] coins to receive a new offer.

Return _the minimum number of coins needed to acquire all the fruits_.

 

Example 1:

Input: prices = [3,1,2]
Output: 4
Explanation: You can acquire the fruits as follows:
- Purchase the 1st fruit with 3 coins, you are allowed to take the 2nd fruit for free.
- Purchase the 2nd fruit with 1 coin, you are allowed to take the 3rd fruit for free.
- Take the 3rd fruit for free.
Note that even though you were allowed to take the 2nd fruit for free, you purchased it because it is more optimal.
It can be proven that 4 is the minimum number of coins needed to acquire all the fruits.

Example 2:

Input: prices = [1,10,1,1]
Output: 2
Explanation: You can acquire the fruits as follows:
- Purchase the 1st fruit with 1 coin, you are allowed to take the 2nd fruit for free.
- Take the 2nd fruit for free.
- Purchase the 3rd fruit for 1 coin, you are allowed to take the 4th fruit for free.
- Take the 4th fruit for free.
It can be proven that 2 is the minimum number of coins needed to acquire all the fruits.

 

Constraints:

• 1 <= prices.length <= 1000
• 1 <= prices[i] <= 105

Solutions

Solution 1

class Solution:
  def minimumCoins(self, prices: List[int]) -> int:
    @cache
    def dfs(i: int) -> int:
      if i * 2 >= len(prices):
        return prices[i - 1]
      return prices[i - 1] + min(dfs(j) for j in range(i + 1, i * 2 + 2))

    return dfs(1)

class Solution {
  private int[] prices;
  private int[] f;
  private int n;

  public int minimumCoins(int[] prices) {
    n = prices.length;
    f = new int[n + 1];
    this.prices = prices;
    return dfs(1);
  }

  private int dfs(int i) {
    if (i * 2 >= n) {
      return prices[i - 1];
    }
    if (f[i] == 0) {
      f[i] = 1 << 30;
      for (int j = i + 1; j <= i * 2 + 1; ++j) {
        f[i] = Math.min(f[i], prices[i - 1] + dfs(j));
      }
    }
    return f[i];
  }
}

class Solution {
public:
  int minimumCoins(vector<int>& prices) {
    int n = prices.size();
    int f[n + 1];
    memset(f, 0x3f, sizeof(f));
    function<int(int)> dfs = [&](int i) {
      if (i * 2 >= n) {
        return prices[i - 1];
      }
      if (f[i] == 0x3f3f3f3f) {
        for (int j = i + 1; j <= i * 2 + 1; ++j) {
          f[i] = min(f[i], prices[i - 1] + dfs(j));
        }
      }
      return f[i];
    };
    return dfs(1);
  }
};

func minimumCoins(prices []int) int {
  n := len(prices)
  f := make([]int, n+1)
  var dfs func(int) int
  dfs = func(i int) int {
    if i*2 >= n {
      return prices[i-1]
    }
    if f[i] == 0 {
      f[i] = 1 << 30
      for j := i + 1; j <= i*2+1; j++ {
        f[i] = min(f[i], dfs(j)+prices[i-1])
      }
    }
    return f[i]
  }
  return dfs(1)
}

function minimumCoins(prices: number[]): number {
  const n = prices.length;
  const f: number[] = Array(n + 1).fill(0);
  const dfs = (i: number): number => {
    if (i * 2 >= n) {
      return prices[i - 1];
    }
    if (f[i] === 0) {
      f[i] = 1 << 30;
      for (let j = i + 1; j <= i * 2 + 1; ++j) {
        f[i] = Math.min(f[i], prices[i - 1] + dfs(j));
      }
    }
    return f[i];
  };
  return dfs(1);
}

Solution 2

class Solution:
  def minimumCoins(self, prices: List[int]) -> int:
    n = len(prices)
    for i in range((n - 1) // 2, 0, -1):
      prices[i - 1] += min(prices[i : i * 2 + 1])
    return prices[0]

class Solution {
  public int minimumCoins(int[] prices) {
    int n = prices.length;
    for (int i = (n - 1) / 2; i > 0; --i) {
      int mi = 1 << 30;
      for (int j = i; j <= i * 2; ++j) {
        mi = Math.min(mi, prices[j]);
      }
      prices[i - 1] += mi;
    }
    return prices[0];
  }
}

class Solution {
public:
  int minimumCoins(vector<int>& prices) {
    int n = prices.size();
    for (int i = (n - 1) / 2; i; --i) {
      prices[i - 1] += *min_element(prices.begin() + i, prices.begin() + 2 * i + 1);
    }
    return prices[0];
  }
};

func minimumCoins(prices []int) int {
  for i := (len(prices) - 1) / 2; i > 0; i-- {
    prices[i-1] += slices.Min(prices[i : i*2+1])
  }
  return prices[0]
}

function minimumCoins(prices: number[]): number {
  for (let i = (prices.length - 1) >> 1; i; --i) {
    prices[i - 1] += Math.min(...prices.slice(i, i * 2 + 1));
  }
  return prices[0];
}

Solution 3

class Solution:
  def minimumCoins(self, prices: List[int]) -> int:
    n = len(prices)
    q = deque()
    for i in range(n, 0, -1):
      while q and q[0] > i * 2 + 1:
        q.popleft()
      if i <= (n - 1) // 2:
        prices[i - 1] += prices[q[0] - 1]
      while q and prices[q[-1] - 1] >= prices[i - 1]:
        q.pop()
      q.append(i)
    return prices[0]

class Solution {
  public int minimumCoins(int[] prices) {
    int n = prices.length;
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = n; i > 0; --i) {
      while (!q.isEmpty() && q.peek() > i * 2 + 1) {
        q.poll();
      }
      if (i <= (n - 1) / 2) {
        prices[i - 1] += prices[q.peek() - 1];
      }
      while (!q.isEmpty() && prices[q.peekLast() - 1] >= prices[i - 1]) {
        q.pollLast();
      }
      q.offer(i);
    }
    return prices[0];
  }
}

class Solution {
public:
  int minimumCoins(vector<int>& prices) {
    int n = prices.size();
    deque<int> q;
    for (int i = n; i; --i) {
      while (q.size() && q.front() > i * 2 + 1) {
        q.pop_front();
      }
      if (i <= (n - 1) / 2) {
        prices[i - 1] += prices[q.front() - 1];
      }
      while (q.size() && prices[q.back() - 1] >= prices[i - 1]) {
        q.pop_back();
      }
      q.push_back(i);
    }
    return prices[0];
  }
};

func minimumCoins(prices []int) int {
  n := len(prices)
  q := Deque{}
  for i := n; i > 0; i-- {
    for q.Size() > 0 && q.Front() > i*2+1 {
      q.PopFront()
    }
    if i <= (n-1)/2 {
      prices[i-1] += prices[q.Front()-1]
    }
    for q.Size() > 0 && prices[q.Back()-1] >= prices[i-1] {
      q.PopBack()
    }
    q.PushBack(i)
  }
  return prices[0]
}

// template
type Deque struct{ l, r []int }

func (q Deque) Empty() bool {
  return len(q.l) == 0 && len(q.r) == 0
}

func (q Deque) Size() int {
  return len(q.l) + len(q.r)
}

func (q *Deque) PushFront(v int) {
  q.l = append(q.l, v)
}

func (q *Deque) PushBack(v int) {
  q.r = append(q.r, v)
}

func (q *Deque) PopFront() (v int) {
  if len(q.l) > 0 {
    q.l, v = q.l[:len(q.l)-1], q.l[len(q.l)-1]
  } else {
    v, q.r = q.r[0], q.r[1:]
  }
  return
}

func (q *Deque) PopBack() (v int) {
  if len(q.r) > 0 {
    q.r, v = q.r[:len(q.r)-1], q.r[len(q.r)-1]
  } else {
    v, q.l = q.l[0], q.l[1:]
  }
  return
}

func (q Deque) Front() int {
  if len(q.l) > 0 {
    return q.l[len(q.l)-1]
  }
  return q.r[0]
}

func (q Deque) Back() int {
  if len(q.r) > 0 {
    return q.r[len(q.r)-1]
  }
  return q.l[0]
}

func (q Deque) Get(i int) int {
  if i < len(q.l) {
    return q.l[len(q.l)-1-i]
  }
  return q.r[i-len(q.l)]
}

function minimumCoins(prices: number[]): number {
  const n = prices.length;
  const q = new Deque<number>();
  for (let i = n; i; --i) {
    while (q.getSize() && q.frontValue()! > i * 2 + 1) {
      q.popFront();
    }
    if (i <= (n - 1) >> 1) {
      prices[i - 1] += prices[q.frontValue()! - 1];
    }
    while (q.getSize() && prices[q.backValue()! - 1] >= prices[i - 1]) {
      q.popBack();
    }
    q.pushBack(i);
  }
  return prices[0];
}

class Node<T> {
  value: T;
  next: Node<T> | null;
  prev: Node<T> | null;

  constructor(value: T) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class Deque<T> {
  private front: Node<T> | null;
  private back: Node<T> | null;
  private size: number;

  constructor() {
    this.front = null;
    this.back = null;
    this.size = 0;
  }

  pushFront(val: T): void {
    const newNode = new Node(val);
    if (this.isEmpty()) {
      this.front = newNode;
      this.back = newNode;
    } else {
      newNode.next = this.front;
      this.front!.prev = newNode;
      this.front = newNode;
    }
    this.size++;
  }

  pushBack(val: T): void {
    const newNode = new Node(val);
    if (this.isEmpty()) {
      this.front = newNode;
      this.back = newNode;
    } else {
      newNode.prev = this.back;
      this.back!.next = newNode;
      this.back = newNode;
    }
    this.size++;
  }

  popFront(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.front!.value;
    this.front = this.front!.next;
    if (this.front !== null) {
      this.front.prev = null;
    } else {
      this.back = null;
    }
    this.size--;
    return value;
  }

  popBack(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.back!.value;
    this.back = this.back!.prev;
    if (this.back !== null) {
      this.back.next = null;
    } else {
      this.front = null;
    }
    this.size--;
    return value;
  }

  frontValue(): T | undefined {
    return this.front?.value;
  }

  backValue(): T | undefined {
    return this.back?.value;
  }

  getSize(): number {
    return this.size;
  }

  isEmpty(): boolean {
    return this.size === 0;
  }
}