Skip to content

2431. Maximize Total Tastiness of Purchased Fruits 👍

Approach 1: 2D DP

  • Time: $O(|\texttt{price}||\texttt{maxAmount}||\texttt{maxCoupons}|)$
  • Space: $O(|\texttt{price}||\texttt{maxAmount}||\texttt{maxCoupons}|)$
 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
37
38
class Solution {
 public:
  int maxTastiness(vector<int>& price, vector<int>& tastiness, int maxAmount,
                   int maxCoupons) {
    const int n = price.size();
    // dp[i][j][k] := the maximum tastiness of the first i price with j amount
    // of money and k coupons
    vector<vector<vector<int>>> dp(
        n + 1, vector<vector<int>>(maxAmount + 1, vector<int>(maxCoupons + 1)));

    for (int i = 1; i <= n; ++i) {
      // 1-indexed
      const int currPrice = price[i - 1];
      const int currTastiness = tastiness[i - 1];
      for (int amount = 0; amount <= maxAmount; ++amount) {
        for (int coupon = 0; coupon <= maxCoupons; ++coupon) {
          // 1. Don't buy, the tastiness will be the same as the first i - 1
          // price.
          dp[i][amount][coupon] = dp[i - 1][amount][coupon];

          // 2. Buy without coupon if have enough money.
          if (amount >= currPrice)
            dp[i][amount][coupon] =
                max(dp[i][amount][coupon],
                    dp[i - 1][amount - currPrice][coupon] + currTastiness);

          // 3. Buy with coupon if have coupon and enough money.
          if (coupon > 0 && amount >= currPrice / 2)
            dp[i][amount][coupon] = max(
                dp[i][amount][coupon],
                dp[i - 1][amount - currPrice / 2][coupon - 1] + currTastiness);
        }
      }
    }

    return dp[n][maxAmount][maxCoupons];
  }
};

 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 maxTastiness(int[] price, int[] tastiness, int maxAmount, int maxCoupons) {
    final int n = price.length;
    // dp[i][j][k] := the maximum tastiness of the first i price with j amount
    // of money and k coupons
    int[][][] dp = new int[price.length + 1][maxAmount + 1][maxCoupons + 1];

    for (int i = 1; i <= n; ++i) {
      // 1-indexed
      final int currPrice = price[i - 1];
      final int currTastiness = tastiness[i - 1];
      for (int amount = 0; amount <= maxAmount; ++amount) {
        for (int coupon = 0; coupon <= maxCoupons; ++coupon) {
          // 1. Don't buy, the tastiness will be the same as the first i - 1
          // price.
          dp[i][amount][coupon] = dp[i - 1][amount][coupon];

          // 2. Buy without coupon if have enough money.
          if (amount >= currPrice)
            dp[i][amount][coupon] = Math.max(dp[i][amount][coupon],
                                             dp[i - 1][amount - currPrice][coupon] + currTastiness);

          // 3. Buy with coupon if have coupon and enough money.
          if (coupon > 0 && amount >= currPrice / 2)
            dp[i][amount][coupon] =
                Math.max(dp[i][amount][coupon],
                         dp[i - 1][amount - currPrice / 2][coupon - 1] + currTastiness);
        }
      }
    }

    return dp[n][maxAmount][maxCoupons];
  }
}

 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
37
38
class Solution:
  def maxTastiness(
      self,
      price: list[int],
      tastiness: list[int],
      maxAmount: int,
      maxCoupons: int,
  ) -> int:
    n = len(price)
    # dp[i][j][k] := the maximum tastiness of the first i price with j amount of
    # money and k coupons
    dp = [[[0] * (maxCoupons + 1)
           for j in range(maxAmount + 1)]
          for i in range(n + 1)]

    for i in range(1, n + 1):
      # 1-indexed
      currPrice = price[i - 1]
      currTastiness = tastiness[i - 1]
      for amount in range(maxAmount + 1):
        for coupon in range(maxCoupons + 1):
          # 1. Don't buy, the tastiness will be the same as the first i - 1
          # price.
          dp[i][amount][coupon] = dp[i - 1][amount][coupon]

          # 2. Buy without coupon if have enough money.
          if amount >= currPrice:
            dp[i][amount][coupon] = max(
                dp[i][amount][coupon],
                dp[i - 1][amount - currPrice][coupon] + currTastiness)

          # 3. Buy with coupon if have coupon and enough money.
          if coupon > 0 and amount >= currPrice // 2:
            dp[i][amount][coupon] = max(
                dp[i][amount][coupon],
                dp[i - 1][amount - currPrice // 2][coupon - 1] + currTastiness)

    return dp[n][maxAmount][maxCoupons]

Approach 2: 1D DP

  • Time: $O(|\texttt{price}||\texttt{maxAmount}||\texttt{maxCoupons}|)$
  • Space: $O(|\texttt{maxAmount}||\texttt{maxCoupons}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int maxTastiness(vector<int>& price, vector<int>& tastiness, int maxAmount,
                   int maxCoupons) {
    // dp[j][k] := the maximum tastiness of price so far with j amount of money
    // and k coupons
    vector<vector<int>> dp(maxAmount + 1, vector<int>(maxCoupons + 1));

    for (int i = 0; i < price.size(); ++i)
      for (int j = maxAmount; j >= price[i] / 2; --j)
        for (int k = maxCoupons; k >= 0; --k) {
          const int buyWithCoupon =
              k == 0 ? 0 : dp[j - price[i] / 2][k - 1] + tastiness[i];
          const int buyWithoutCoupon =
              j < price[i] ? 0 : dp[j - price[i]][k] + tastiness[i];
          dp[j][k] = max({dp[j][k], buyWithCoupon, buyWithoutCoupon});
        }

    return dp[maxAmount][maxCoupons];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int maxTastiness(int[] price, int[] tastiness, int maxAmount, int maxCoupons) {
    // dp[j][k] := the maximum tastiness of price so far with j amount of money and k
    // coupons
    int[][] dp = new int[maxAmount + 1][maxCoupons + 1];

    for (int i = 0; i < price.length; ++i)
      for (int j = maxAmount; j >= price[i] / 2; --j)
        for (int k = maxCoupons; k >= 0; --k) {
          final int buyWithCoupon = k == 0 ? 0 : dp[j - price[i] / 2][k - 1] + tastiness[i];
          final int buyWithoutCoupon = j < price[i] ? 0 : dp[j - price[i]][k] + tastiness[i];
          dp[j][k] = Math.max(dp[j][k], Math.max(buyWithCoupon, buyWithoutCoupon));
        }

    return dp[maxAmount][maxCoupons];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def maxTastiness(
      self,
      price: list[int],
      tastiness: list[int],
      maxAmount: int,
      maxCoupons: int,
  ) -> int:
    # dp[j][k] := the maximum tastiness of price so far with j amount of money and k coupons
    dp = [[0] * (maxCoupons + 1) for _ in range(maxAmount + 1)]

    for p, t in zip(price, tastiness):
      for j in range(maxAmount, p // 2 - 1, -1):
        for k in range(maxCoupons, -1, -1):
          buyWithCoupon = 0 if k == 0 else dp[j - p // 2][k - 1] + t
          buyWithoutCoupon = 0 if j < p else dp[j - p][k] + t
          dp[j][k] = max(dp[j][k], buyWithCoupon, buyWithoutCoupon)

    return dp[maxAmount][maxCoupons]