# 2431. Maximize Total Tastiness of Purchased Fruits
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/maximize-total-tastiness-of-purchased-fruits/description/
## 思路
背包问题dp[i][j][k]表示物品0:i在花掉j和k个coupon之后能实现的最大tastiness
对于每一个物品 有三种可能性
1. 不买它 dp[i][j][k] = dp[i-1][j][k]
2. 买它但不用券 dp[i][j][k] = dp[i-1][j-price[i]][k]
3. 买它用券 dp[i][j][k] = dp[i-1][j-price[i]/2][k-1]

可以做空间优化
## Code

class Solution {
    public int maxTastiness(int[] price, int[] tastiness, int maxAmount, int maxCoupons) {
        int n = price.length;
        int[][][] dp = new int[n+1][maxAmount+1][maxCoupons+1];
        for(int i=1; i<=n; i++){
            for(int j=0; j<=maxAmount; j++){
                for(int k=0; k<=maxCoupons; k++){
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j-price[i-1]>=0){
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j-price[i-1]][k]+tastiness[i-1]);
                    }
                    if(k>0 && j-price[i-1]/2>=0){
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j-price[i-1]/2][k-1]+tastiness[i-1]);
                    }
                }
            }
        }
        return dp[n][maxAmount][maxCoupons];
    }
}